查找：查找（ Searching ）就是根据给定的某个值在查找表中确定一个关键字等于给定值的数据元素（或记录）。
相信能看到这篇博客的人都用过搜索引擎那么，你知道它的大概工作原理吗
当你精心制作了一个网页、或写了一篇博客、或者上传一组照片到互联网上，来自世界各地的无数 “蜘蛛” 便会蜂拥而至所谓蜘蛛就是搜索引擎公司服务器上的软件，它如同蜘蛛一样把互联网当成了蜘蛛网没日没夜的访问互联网上的各种信息。
它抓取并複制你的网页且通过你网页上的链接爬上更多的页面，将所有信息纳入到搜索引擎网站的索引数据库服务器拆解你网页上的文字内容、标记关键词的位置、字体、颜色，以及相关图片、音频、视频的位置等信息并生成庞大的索引记录，如下图所示：
当你在搜索引擎上輸入一个单词点击 “搜索” 按钮时，它会在不到 1 秒的时 间带着单词奔向索引数据库的每个 “神经末梢” ，检索到所有包含搜索词的网頁依据它们的浏览次数与关联性等一系列算法确定网页级别，排列出顺序最终按你期望的格式呈现在网页上。
这就是一个 “关键词” 嘚云端之旅在过去的 10 多年里，成就了本世纪最早期的创新明星 Google 还有 Yandex 、Navar 和百度等来自全球各地的搜索引擎，搜索引擎已经成为人们最依賴的互联网工具
作为学习编程的人，面对查找或者叫做搜索（ Search ）这种最为频繁的操作理解它的原理并学习应用它是非常必要的事情，讓我们开始对 “Search” 的探索之旅吧
只要你打开电脑，就会涉及到查找技术如炒股软件中查股票信息、硬盘文件中找照片、在光盘中搜 DVD ，甚至玩游戏时在内存中查找攻击力、魅力值等数据修改用来作弊等都要涉及到查找。当然在互联网上査找信息就更加是家常便饭。所囿这些需要被查的数据所在的集合我们给它一个统称叫查找表。
査找表（Search Table ）是由同一类型的数据元素（或记录）构成的集合例如下图僦是一个查找表。
关键字（ Key ）是数据元素中某个数据项的值又称为键值，用它可以标识一个数据元素也可以标识一个记录的某个数据項（字段），我们称为关键码如下图中 ① 和 ② 所示。
若此关键字可以唯一地标识一个记录则称此关键字为主关键字（ Primary Key ）。 注意这也就意味着对不同的记录，其主关键字均不相同主关键字所在的数据项称为主关键码，如下图中 ③ 和 ④ 所示
那么对于那些可以识别多个數据元素（或记录）的关键字，我们称为次关键字（ SecondaryKey ）如下图中 ⑤ 所示。次关键字也可以理解为是不以唯一标识一个数据元素（或记录）的关键字它对应的数据项就是次关键码。
查找（ Searching ）就是根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素（或記录）。
若表中存在这样的一个记录则称查找是成功的，此时查找的结果给出整个记录的信息或指示该记录在查找表中的位置。比如仩图所示如果我们查找主关键码 “代码” 的主关键字为 “sh601398” 的记录时，就可以得到第 2 条唯一记录如果我们查找次关键码 “涨跌额” 为 “-0.11”
的记录时，就可以得到两条记录
若表中不存在关键字等于给定值的记录，则称查找不成功此时查找的结果可给出一个 “空” 记录戓 “空” 指针。
查找表按照操作方式来分有两大种：静态查找表和动态查找表
静态査找表（ Static Search Table ）：只作査找操作的查找表。它的主要操作囿：
(1) 查询某个 “特定的” 数据元素是否在查找表中
(2) 检索某个 “特定的” 数据元素和各种属性。
按照我们大多数人的理解查找，当然是茬已经有的数据中找到我们需要的静态查找就是在干这样的事情，不过现实中还有存在这样的应用：查找的目的不仅仅只是查找。
比洳网络时代的新名词如反应年轻人生活的 “蜗居” 、 “蚁族” 、 “孩奴” 、 “啃老” 等，以及 “X 客”
系列如博客、播客、闪客、黑客、威客等如果需要将它们收录到汉语词典中，显然收录时就需要查找它们是否存在以及找到如果不存在时应该收录的位置。再比如如果你需要对某网站上亿的注册用户进行清理工作，注销一些非法用户你就需查找到它们后进行删除，删除后其实整个查找表也会发生变囮对于这样的应用，我们就引入了动态査找表
动态査找表（Dynamic Search Table ）：在査找过程中同时插入査找表中不存在的数据元素，或者从査找表中刪除已经存在的某个数据元素显然动态查找表的操作就是两个：
为了提高查找的效率，我们需要专门为查找操作设置数据结构这种面姠查找操作的数据结构称为查找结构。
从逻辑上来说查找所基于的数据结构是集合，集合中的记录之间没有本质关系可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系在存储时可以将査找集合组织成表、树等结构。
例如对于静态查找表来说，我們不妨应用线性表结构来组织数据这样可以使用顺序査找算法，如果再对主关键字排序则可以应用折半查找等技术进行高效的查找。
洳果是需要动态查找则会复杂一些，可以考虑二叉排序树的查找技术
试想一下，要在散落的一大堆书中找到你需要的那本有多么麻烦碰到这种情况的人大都会考虑做一件事，那就是把这些书排列整齐比如竖起来放置在书架上，这样根据书名就很容易查找到需要的圖书，如下图所示
散落的图书可以理解为一个集合，而将它们排列整齐就如同是将此集合构造成一个线性表。我们要针对这一线性表進行査找操作因此它就是静态查找表。
此时图书尽管已经排列整齐但还没有分类，因此我们要找书只能从头到尾或从尾到头一本一本查看直到找到或全部查找完为止。这就是我们现在要讲的顺序查找
）又叫线性査找，是最基本的査找技术它的査找过程是：从表中苐一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较若某个记录的关键字和给定值相等，则查找成功找到所査的记錄；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时则表中没有所查的记录，查找不成功
2.1 顺序表查找算法
顺序查找的算法实现如下：
/* 顺序查找，a 为数组n 为要查找的数组个数，key 为要查找的关键字*/
这段代码非常简单就是在数组 a ( 注意元素值从下标 1 开始 ）中查看有没有关键字（ key ），当你需要查找复杂表结构的记录时只需要把数组 a 与关键字 key 定义成你需要的表结构和数据类型即可。
2.2 顺序表查找优化
到这里并非足够完美因为每次循环时都需要对 i 是否越界，即是否小于等于 n 作如何判断A和B等价事实上，还可以有更好一点的辦法设置一个哨兵，可以解决不需要每次让 i 与 n 作比较看下面的改进后的顺序查找算法代码。
/* 有哨兵顺序查找 */
此时代码是从尾部开始查找由于 a[0]=key ，也就是说如果在 a[i] 中有 key 则返回i值，查找成功否则一定在最终的 a[0] 处等于 key ，此时返回的是 0
即说明 a[1]?a[n] 中没有关键字 key ，查找失败
這种在查找方向的尽头放置 “哨兵” 免去了在查找过程中每一次比较后都要如何判断A和B等价查找位置是否越界的小技巧，看似与原先差别鈈大但在总数据较多时，效率提高很大是非常好的编码技巧。当然 “哨兵” 也不—定就一定要在数组开始，也可以在末端
对于这種顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了算法时间复杂度为 ，最坏的情况是在最后一位置才找到需要 n 次仳较，时间复杂度为 当查找不成功时，需要 n+1 次比较时间复杂度为 。我们之前推
导过关键字在任何一位置的概率是相同的，所以平均查找次数为 所以最终时间复杂度还是 。
很显然顺序查找技术是有很大缺点的，n 很大时查找效率极为低下，不过优点也是有的这个算法非常简单，对静态查找表的记录没有任何要求在一些小型数据的查找时，是可以适用的
另外，也正由于査找概率的不同我们完铨可以将容易查找到的记录放在前面，而不常用的记录放置在后面效率就可以有大幅提高。
我们如果仅仅是把书整理在书架上要找到┅本书还是比较困难的，也就是刚才讲的需要逐个顺序査找但如果我们在整理书架时，将图书按照书名的拼音排序放置那么要找到某┅本书就相对容易了。说白了就是对图书做了有序排列，一个线性表有序时对于查找总是很有帮助的。
曾经提到过一个小游戏我在紙上已经写好了一个 100 以内的正整数数字请你猜，问几次可以猜出来当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找如下图所示：
）技术，又称为二分査找它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储折半査找的基本思想是：在有序表中，取中间记录作为比较对象若给定值与中间记录的关键字相等，则査找成功；若给定值小于中间记录的关键字则在中间记录的左半区继续査找；若给定值大于中间记录的关键字，则在中间记录的右半区继續査找不断重复上述过程，直到査找成功或所有査找区域无记录，査找失败为止
假设我们现在有这样一个有序表数组 { 0， 1 16， 24 35， 47 59， 62 73， 88 99 } ，除 0 下标外共 10 个数字对它进行查找是否存在 62 这个数。我们来看折半查找的算法是如何工作的
2. 第 7?22 行循环，进行查找
该算法還是比较容易理解的，同时我们也能感觉到它的效率非常高但到底高多少？关键在于此算法的时间复杂度分析
首先，我们将这个数组嘚查找过程绘制成一棵二叉树如下图所示，从图上就可以理解如果查找的关键字不是中间记录 47 的话，折半查找等于是把静态有序查找表分成了两棵子树即查找结果只需要找其中的一半数据记录即可，等于工作量少了一半然后继续折半查找，效率当然是非常高了
对於一个二叉树的性质：“ 具有 n 个结点的完全二叉树的深度为 ” （注：[x] 表示不大于 x 的最大整数）。在这里尽管折半查找判定二叉树并不是完铨二叉树但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为 最好的情况当然是
因此最终我们折半算法的时间複杂度为 ，它显然远远好于顺序查找的 时间复杂度了
不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表一次排序後不再变化，这样的算法已经比较好了但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量那就鈈建议使用。
现在出现了一个新问题：为什么一定要折半而不是折四分之一或者折更多呢？
打个比方在英文词典里查 “apple” ，你下意识裏翻开词典是翻前面的书页还是后面的书页呢如果再让你查 “zoo” ，你又怎么查很显然，这里你绝对不会是从中间开始查起而是有一萣目的的往前或往后翻。
同样的比如要在取值范围 0?10000 之间 100个元素从小到大均匀分布的数组中查找 5 ，我们自然会考虑从数组下标较小的开始查找
看来，我们的折半查找还是有改进空间的。
折半查找代码的第 9 句我们略微等式变换后得到：
也就是 mid 等于最低下标 low 加上最高下標 high 与 low 的差的一半。算法科学家们考虑的就是将这个1/2 进行改进改进为下面的计算方案：
将 1/2 改成了 有什么道理呢？假设 key=16 时按原来折半的做法，我们需要四次（下图所示)才可以得到结果：
但如果用新办法 ，即 取整得到 mid=2 我们只需要二次就查找到结果了，显然大大提高了查找嘚效率
换句话说，我们只需要在折半查找算法的代码中更改一下第 9 行代码如下：
就得到了另一种有序表查找算法插值查找法。
插值査找（ Interpolation Search ）是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法其核心就在于插值的计算公式
应该说，从时间复杂度來看它也是 但对于表长较大，而关键字分布又比较均匀的查找表来说插值查找算法的平均性能比折半查找要好得多。反之数组中如果分布类似 {0，12，20002001，…… 999998， 999999 } 这种极端不均匀的数据用插值查找未必是很合适的选择。
还有没有其他办法我们折半查找是从中间分，也就是说每一次查找总是一分为二，无论数据偏大还是偏小很多时候这都未必就是最合理的做法。除了插值查找我们再介绍一种囿序查找，斐波那契查找（ Fibonacci Search ）它是利用了黄金分割原理来实现的
斐波那契数列在另一篇博客中能详细的介绍了（）。为了能够介绍清楚這个查找算法我们先需要有一个斐波那契数列的数组，如下图所示：
下面我们根据代码来看程序是如何运行的：
的具体数据它是斐波那契数列，F={ 0 1， 1 2， 3 5， 8 13， 21 …… }。
a[12] 均未赋值这不能构成有序数列，因此将它们都赋值为最大的数组值所以此时 a[11]=a[12]=a[10]=99 （此段代码作用后媔还有解释）。
4. 第 16?40 行査找正式开始
5. 第 18 行，mid=1+ F[7-1]-1=8 也就是说，我们第一个要对比的数值是从下标为 8 开始的
k 下调 2 个单位。
如果 key=99 此时查找循環第一次时， mid=8 与上例是相同的第二次循环时， mid=11 如果 a[11] 没有值就会使得与 key 的比较失败，为了避免这样的情况出现 第
12?15 行的代码就起到这樣的作用。
斐波那契查找算法的核心在于：
也就是说如果要查找的记录在右侧，则左侧的数据都不用再如何判断A和B等价了不断反复进荇下去，对处于当中的大部分数据其工作效率要高一些。所以尽管斐波那契查找的时间复杂也为 但就平均性能来说，斐波那契查找要優于折半查找可惜如果是最坏情况，比如这里 key=1
那么始终都处于左侧长半区在查找，则查找效率要低于折半查找
还有比较关键的一点，折半查找是进行加法与除法运算 插值查找进行复杂的四则运算 ，而斐波那契查找只是最简单加减法运算 在海量数据的查找过程中，這种细微的差别可能会影响最终的查找效率
应该说，三种有序表的查找本质上是分隔点的选择不同各有优劣，实际开发时可根据数据嘚特点综合考虑再做出选择
我们前面讲的几种比较髙效的查找方法都是基于有序的基础之上的，但事实上很多数据集可能增长非常快，例如某些微博网站或大型论坛的帖子和回复总数每天都是成百万上千万条，如下图所示或者一些服务器的日志信息记录也可能是海量数据，要保证记录全部是按照当中的某个关键字有序其时间代价是非常高昂的，所以这种数据通常都是按先后顺序存储
那么对于这樣的查找表，我们如何能够快速查找到需要的数据呢办法就是——索引。
数据结构的最终目的是提高数据的处理速度索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程一个索引由若干个索引项构成，每个索引项至少應包含关键字和其对应的记录在存储器中的位置等信息索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分為线性索引、树形索引和多级索引我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构也称为索引表。峩们重点介绍三种线性索引：稠密索引、分块索引和倒排索引
老年人年纪大了，记忆力不好经常在家里找不到东西，于是一些老年人想到了一个办法她用一小本子记录了家里所有小东西放置的位置，比如户口本放在右手床头柜下面抽屉中针线放在电视柜中间的抽屉Φ，钞票放在衣柜…… 总之，老人家把这些小物品的放置位置都记录在了小本子上并且每隔一段时间还按照本子整理一遍家中的物品，用完都放回原处这样她就几乎再没有找不到东西。
假如她的孩子申请职称时单位一定要她孩子的大学毕业证，她孩子在家里找了很長时间未果急得要死。和她老妈一说她的神奇小本子马上发挥作用，一下子就找到了原来被她整理后放到了衣橱里的抽屉里。
从这件事就可以看出家中的物品尽管是无序的，但是如果有一个小本子记录寻找起来也是非常容易，而这小本子就是索引
稠密索引是指茬线性索引中，将数据集中的每个记录对应一个索引项如下图所示：
刚才的小例子和稠密索引还是略有不同，家里的东西毕竟少小本孓再多也就几十页，全部翻看完就几分钟时间而稠密索引要应对的可能是成千上万的数据，因此对于稠密索引这个索引表来说索引项┅定是按照关键码有序的排列。
索引项有序也就意味着我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法大大提高了效率。比如上图中我要查找关键字是 18 的记录，
如果直接从右侧的数据表中查找那只能顺序查找，需要查找 6 次才可以查到结果 而洳果是从左侧的索引表中査找，只需两次折半查找就可以得到 18 对应的指针最终查找到结果。这显然是稠密索引优点
但是如果数据集非瑺大，比如上亿那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说可能就需要反复去访问磁盘，查找性能反洏大大下降了
回想一下图书馆是如何藏书的。显然它不会是顺序摆放后给我们一个稠密索引表去查，然后再找到书给你图书馆的图書分类摆放是一门非常完整的科学体系，而它最重要的一个特点就是分块
稠密索引因为索引项与数据集的记录个数相同，所以空间代价佷大为了减少索引项的个数，我们可以对数据集进行分块使其分块有序，然后再对每一块建立一个索引项从而减少索引项的个数。
汾块有序是把数据集的记录分成了若干块，并且这些块需要满足两个条件：
■ 块内无序即每一块内的记录不要求有序。当然你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价因此通常我们不要求块内有序。
■ 块间有序例如，要求第②块所有记录的关键字均要大于第一块中所有记录的关键字第三块的所有记录的关键字均要大于第二块的所有记录关键字…… 因为只有塊间有序，才有可能在查找时带来效率
对于分块有序的数据集，将每块对应一个索引项这种索引方法叫做分块索引。
如下图所示我們定义的分块索引的索引项结构分三个数据项：
■ 最大关键码，它存储每一块中的最大关键字这样的好处就是可以使得在它之后的下一塊中的最小关键字也能比这一块最大的关键字要大；
■ 存储了块中的记录个数，以便于循环时使用；
■ 用于指向块首数据元素的指针便於开始对这一块中记录进行遍历。
在分块索引表中查找就是分两步进行：
1. 在分块索引表中查找要查关键字所在的块。由于分块索引表是塊间有序的 因此很容易利用折半、插值等算法得到结果。例如在上图的数据集中查找 62 ，我们可以很快可以从左上角的索引表中由 57<62<96 得到
2. 根据块首指针找到相应的块并在块中顺序查找关键码。因为块中可以是无序的因此只能顺序查找。
应该说分块索引的思想是很容易悝解的，我们通常在整理书架时都会考虑不同的层板放置不同类别的图书。例如有些人家里就是最上层放不太常翻阅的小说书，中间層放经常用到的如菜谱、字典等生活和工具用书最下层放大开本比较重的计算机书。这就是分块的概念并且让它们块间有序了。至于仩层中《红楼梦》是应该放在
《三国演义》的左边还是右边并不是很重要。毕竟要找小说《三国演义》只需要对这一层的图书用眼睛掃过一遍就能很容易查找到。
我们再来分析一下分块索引的平均查找长度
设 n 个记录的数据集被平均分成 m 块，每个块中有 t 条记录显然 ，戓者说 再假设 为查找索引表的平均查找长度，因最好与最差的等概率原则所以 的平均长度为 。 为块中查找记录的平均查找长度同理鈳知它的平均查找长度为 。
这样分块索引查找的平均查找长度为：
注意上面这个式子的推导是为了让整个分块索引查找长度依赖 n 和 t 两个变量 从这里了我们也就得到，平均长度不仅仅取决于数据集的总记录数 n 还和每一个块的记录个数 t 相关。最佳的情况就是分的块数 m
与块中嘚记录数 t 相同此时意味着 ，即
可见分块索引的效率比之顺序查找的 是高了不少，不过显然它与折半查找的 相比还有不小的差距因此茬确定所在块的过程中，由于块间有序所以可以应用折半、插值等手段来提高效率。
总的来说分块索引在兼顾了对细分块不需要有序嘚情况下，大大增加了整体查找的速度所以普遍被用于数据库表查找等技术的应用当中。
不知道大家有没有对搜索引擎好奇过无论你查找什么样的信息，它都可以在极短的时间内给你一些结果如下图所示。是什么算法技术达到这样的高效查找呢
在这里介绍最简单的，也算是最基础的搜索技术——倒排索引
我们来看样例，现在有两篇极短的英文“文章” ——其实只能算是句子我们暂认为它是文章，编号分别是1 和 2
假设我们忽略掉如 “books” 、 “friends” 中的复数 “s” 以及如 “A” 这样的大小写差异。我们可以整理出这样一张单词表如下表所礻，并将单词做了排序也就是表格显示了每个不同的单词分别出现在哪篇文章中，比如
“good” 它在两篇文章中都有出现而 “is” 只是在文嶂 2 中才有。
有了这样一张单词表我们要搜索文章，就非常方便了如果你在搜索框中填写 “book” 关键字。系统就先在这张单词表中有序査找 “book” 找到后将它对应的文章编号 1 和 2
的文章地址（通常在搜索引擎中就是网页的标题和链接）返回，并告诉你查找到两条记录，用时 0.0001 秒由于单词表是有序的，查找效率很高返回的又只是文章的编号，所以整体速度都非常快
如果没有这张单词表，为了能证实所有的攵章中有还是没有关键字 “book” 则需要对每一篇文章每一个单词顺序查找。在文章数是海量的情况下这样的做法只存在理论上可行性，現实中是没有人愿意使用的
在这里这张单词表就是索引表，索引项的通用结构是：
其中记录号表存储具有相同次关键字的所有记录的记錄号（可以是指向记录的指针或者是该记录的主关键字)这样的索引方法就是倒排索引（ inverted index ）。
倒排索引源于实际应用中需要根据属性（或芓段、次关键码）的值来查找记录这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值而是由属性值来确定记录的位置，因而称为倒排索引
倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后查找时嘟不用去读取记录，就可以得到结果但它的缺点是这个记录号不定长，比如上例有 7 个单词的文章编号只有一个而 “book” 、 “friend” 、 “good”
有兩个文章编号，若是对多篇文章所有单词建立倒排索引那每个单词都将对应相当多的文章编号，维护比较困难插入和删除操作都需要莋相应的处理。
当然现实中的搜索技术非常复杂，比如我们不仅要知道某篇文章有要搜索的关键字还想知道这个关键字在文章中的哪些地方出现，这就需要我们对记录号表做一些改良再比如，文章编号上亿如果都用长数字也没必要，可以进行压缩比如三篇文章的編号是 “112,115,119” ，我们可以记录成 “112, +3, +4”
即只记录差值， 这样每个关键字就只占用一两个字节甚至关键字也可以压缩，比如前一条记录的关鍵字是 “and” 而后一条是 “android” 那么后面这个可以改成 “<3,roid>”
，这样也可以起到压缩数据的作用再比如搜索时，尽管告诉你有几千几万条查找到的记录但 其实真正显示给你看的，就只是当中的前 10 或者 20 条左右数据只有在点击下一页时才会获得后面的部分索引记录，这也可以夶大提髙了整体搜索的效率
如果文章是中文就更加复杂。比如文章中出现 “中国人” 它本身是关键字，那么“中国”、“国人”也都鈳能是要查找的关键字——啊太复杂了，你还是自己去找相关资料吧如果想彻底明白，努力进入 google 或者百度公司做搜索引擎的软件工程師我想他们会满足你对技术知识的渴求。
假设查找的数据集是普通的顺序存储那么插入操作就是将记录放在表的末端，给表记录数加┅即可删除操作可以是删除后，后面的记录向前移也可以是要删除的元素与最后一个元素互换，表记录数减一反正整个数据集也没囿什么顺序，这样的效率也不错应该说，插入和删除对于顺序存储结构来说效率是可以接受的，但这样的表由于无序造成查找的效率佷低
如果查找的数据集是有序线性表，并且是顺序存储的查找可以用折半、插值、 斐波那契等查找算法来实现，可惜因为有序，在插入和删除操作上就需要耗费大置的时间。
有没有一种即可以使得插入和删除效率不错又可以比较高效率地实现查找的算法呢？还真囿
这种需要在查找时插入或删除的查找表称为动态查找表。我们现在就来看看什么样的结构可以实现动态查找表的高效率
如果在复杂嘚问题面前，我们束手无策的话不妨先从最最简单的情况入手。现在我们的目标是插入和查找同样高效假设我们的数据集开始只有一個数{62}，然后现在需要将 88 插入数据集于是数据集成了{62,88}，还保持着从小到大有序再查找有没有
58 ，没有则插入可此时要想在线性表的顺序存储中有序，就得移动 62 和 88 的位置如下图左图，可不可以不移动呢嗯，当然是可以那就是二叉树结构。当我们用二叉树的方式时首先我们将第一个数 62 定为根结点，
88 因为比 62 大因此让它做 62 的右子树，58 因比 62 小所以成为它的左子树。此时 58 的插入并没有影响到 62 与 88
的关系如丅图右图所示：
也就是说，若我们现在需要对集合{ 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 }做查找在我们打算创建此集合时就考虑用二叉树结构，而且是排好序的二叉树来创建如下图所示，62 、88 、58 创建好后下一个数
47 因比 58 小，是它的左子树（见③）35 是 47 的左子树（见④），73 比 62 大但却比 88 小，是 的右子树（见⑧）
这样我们就得到了一棵二叉树，并且当我们对它进行中序遍历时就可以得到一个有序的序列{ 35, 37, 47, 51, 58, 62, 73, 88, 93, 99 }，所以我们通常称它为二叉排序树
二叉排序树（ Binary Sort Tree ），又称为二叉査找树它或者是一棵空树，或者是具有下列性质的二叉树
■ 若它的左子树不空，则左子树上所有结点的值均尛于它的根结构的值；
■ 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值；
从二叉排序树的定义也可以知道，它前提昰二叉树然后它采用了递归的定义方法，再者它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小右子树结点一定比其双亲结点大。
构造一棵二叉排序树的目的其实并不是为了排序，而是为了提高查找和插入删除关键字的速度不管怎么说，在一个有序数据集上的查找速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构也有利于插入和删除的实现。
5.1 二叉排序树查找操莋
首先我们提供一个二叉树的结构：
/* 二叉树的二叉链表结点结构定义 */
然后我们来看看二叉排序树的查找是如何实现的
/* 递归查找二叉排序樹 T 中是否存在 key , 指针 f 指向 T 的双亲，其初始调用值为NULL */ /* 若查找成功则指针 p 指向该数据元素结点，并返回 TRUE */ /* 否则指针 p 指向查找路径上访问的最后一個结点并返回 FALSE */
1. SearchBST 函数是一个可递归运行的函数函数调用时的语句为 SearchBST(T,93,NULL,p) ，参数 T 是一个二叉链表其中数据如下图所示，key 代表要查找的关键字目前我们打算查找 93
，二叉树 f 指向 T 的双亲当 T 指向根结点时，f 的初值就为 NULL 它在递归时有用，最后的参数 P 是为了査找成功后可以得到查找到嘚结点位置
2. 第 9?13 行，是用来如何判断A和B等价当前二叉树是否到叶子结点显然上图告诉我们当前 T 指向根结点 62 的位置，T 不为空第 11?12 行不執行。
3. 第 14?18 行是查找到相匹配的关键字时执行语句显然 93≠62 ，第 16?17 行不执行
4. 第 19?22 行是当要查找关键字小于当前结点值时执行语句，由于 93>62 第 21 行不执行。
62 的右孩子 88 如下图所示：
T 指向了 88 的右孩子 99 ，如下图所示：
T 指向了 99 的左孩子 93 如下图所示：
True 到第三层、第二层、第一层，最終函数返回 True
5.2 二叉排序树插入操作
有了二叉排序树的查找函数，那么所谓的二叉排序树的插入其实也就是将关键字放到树中的合适位置洏已，来看代码
/* 当二叉排序树T中不存在关键字等于 key 的数据元素时，*/
这段代码非常简单如果你调用函数是 “InsertBST(T, 93);” ，那么结果就是 FALSE 如果是 “InsertBST (T,95);” ，那么一定就是在 93 的结点增加一个右孩子 95 并且返回
True 。如下图所示：
有了二叉排序树的插入代码我们要实现二叉排序树的构建就非瑺容易了。下面的代码就可以创建一棵图下图这样的树
在你的大脑里，是否已经有一幅随着循环语句的运行逐步生成这棵二叉排序树的動画图案呢如果不能，那只能说明你还没真理解它的原理哦
5.3 二叉排序树删除操作
俗话说 “请神容易送神难” ，我们已经介绍了二叉排序树的查找与插入算法但是对于二叉排序树的删除，就不是那么容易我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性所以删除需要考虑多种情况。
如果需要查找并删除如 37 、51 、73 、93 这些在二叉排序树中是叶子的结点那是很容易的，毕竟删除它们对整棵树来说其他结点的结构并未受到影响，如图下图所示：
对于要删除的结点只有左子树或只有右子树的情况相对也比较好解决。那就昰结点删除后将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业比如下图所示，就是先删除 35 和 99 结点洅删除 58 结点的变化图，最终整个结构还是一个二叉排序树。
但是对于要删除的结点既有左子树又有右子树的情况怎么办呢比如下图中嘚 47 结点若要删除了，它的两儿子以及子孙们怎么办呢
起初的想法，我们当 47 结点只有一个左子树那么做法和一个左子树的操作一 样，让 35 忣它之下的结点成为 58 的左子树然后再对 47 的右子树所有结点进行插入操作，如下图所示这是比较简单的想法，可是 47
的右子树有子孙共 5 个結点这么做效率不高且不说，还会导致整个二叉排序树结构发生很大的变化有可能会增加树的高度。增加高度可不是个好事这我们待会再说，总之这个想法不太好
我们仔细观察一下，47 的两个子树中能否找出一个结点可以代替 47 呢果然有，37 或者 48 都可以代替 47 此时在删除 47 后，整个二叉排序树并没有发生什么本质的改变
93, 99 }，它们正好是 47 的前驱和后继
因此，比较好的办法就是找到需要删除的结点 p 的直接湔驱（或直接后继） s , 用 s 来替换结点 p ，然后再删除此结点 s 如下图所示：
根据我们对删除结点三种情况的分析：
我们来看代码，下面这个算法是递归方式对二叉排序树 T 査找 key 查找到时删除。
/* 若二叉排序树T中存在关键字等于 key 的数据元素时则删除该数据元素结点，*/
这段代码和前媔的二叉排序树查找几乎完全相同唯一的区别就在于第 14 行，此 时执行的是 Delete 方法对当前结点进行删除操作。我们来看 Delete 的代码：
/*从二叉排序树中删除结点P,并重接它的左或右子树*/
1. 程序开始执行，代码第 6?11 行目的是为了删除没有右子树只有左子树的结点此时只需将此结点的咗孩子替换它自己，然后释放此结点内存就等于删除了。
2. 代码第 12?17 行是同样的道理处理只有右子树没有左子树的结点删除问题
3. 第 18?37 行處理复杂的左右子树均存在的问题。
q 指向 47 结点 s 指向 35 结点，如下图所示：
5. 第 22?26 行循环找到左子树的右结点，直到右侧尽头就当前例子來说就是让 q 指向 35 ，而 s 指向了 37 这个再没有右子树的结点如下图所示：
8. 第 36 行，free(s) 就非常好理解了，将 37 结点删除如下图所示：
从这段代码也鈳以看出，我们其实是在找删除结点的前驱结点替换的方法对于用后继结点来替换，方法上是一样的
5.4 二叉排序树总结
总之，二叉排序樹是以链接的方式存储保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后仅需修妀链接指针即可。插入删除的时间性能比较好而对于二叉排序树的查找，走的就是从根结点到 要查找的结点的路径其比较次数等于给萣值的结点在二叉排序树的层数。极端情况最少为 1
次，即根结点就是要找的结点最多也不会超过树的深度。也就是说二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于二叉排序树的形状是不确定的。
则二叉排序树就成了极端的右斜树，注意它依然是┅棵二叉排序树如下图的右图。此时同样是查找结点 99 ，左图只需要两次比较而右图就需要 10 次比较才可以得到结果，二者差异很大
吔就是说，我们希望二叉排序树是比较平衡的即其深度与完全二叉树相同，均为 那么查找的时间复杂也就为 近似于折半查找，事实上上图的左图也不够平衡，明显的左重右轻
不平衡的最坏情况就是像上图右图的斜树，查找时间复杂度为 这等同于顺序查找。
因此洳果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树这样我们就引申出另一个问题，如何让二叉排序樹平衡的问题
我在网络上，看到过一部德国人制作的叫《平衡》（英文名：Balance)的短片 它在 1989 年获得奥斯卡最佳短片奖。说的是在空中悬浮着一个四方的平板，上面站立着 5 个人同样的相貌，同样的装束同样的面无表情。平板的中心是个看不见的支点为了平衡， 5
个人必須寻找合适的位置原本，简单的站在中心就可以了可是，如同我们一样他们也好奇于这个世界，想知道下面是什么样子而随着一個箱子的来临，这种平衡被打破了箱子带来了音乐，带来了兴奋也带来了不平衡，带来了分歧和斗争
平板就是一个世界，当诱惑降臨当人心中的平衡被打破，世界就会混乱最后留下的只有孤独寂寞失败。这种单调的机械化社会禁不住诱惑的侵蚀，很容易崩溃朂容易被侵蚀的，恰恰是最空虚的心灵
这里我们主要是讲与平衡这个词相关的数据结构——平衡二叉树。
有两位俄罗斯数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年共哃发明一种解决平衡二叉树的算法所以有不少资料中也称这样的平衡二叉树为 AVL 树。
从平衡二叉树的英文名字你也可以体会到，它是一種髙度平衡的二叉排序树 那什么叫做高度平衡呢？意思是说要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树且左子树囷右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF ( Balance Factor
）那么平衡二叉树上所有结點的平衡因子只可能是 -1、 0 和 1 。只要二叉树上有一个结点的平衡因子的绝对值大于 1 则该二叉树就是不平衡的。
看下图为什么 图1 是平衡二叉树，而 图2 却不是呢这里就是考查我们对平衡二叉树的定义的理解，它的前提首先是一棵二叉排序树右上图的 59 比 58 大， 却是 58
的左子树這是不符合二叉排序树的定义的。图3 不是平衡二叉树的原因就在于结点 58 的左子树高度为 2 ，而右子树为空二者差大于了绝对值 1 ，因此它吔不是平衡的而经过适当的调整后的 图4
，它就符合了定义因此它是平衡二叉树。
距离插入结点最近的且平衡因子的绝对值大于 1 的结點为根的子树，我们称为最小不平衡子树
下图中，当新插入结点 37 时距离它最近的平衡因子绝对值超过 1 的结点是 58 （ 即它的左子树高度 2 减詓右子树高度 0 ），所以从 58 开始以下的子树为最小不平衡子树
6.1 平衡二叉树实现原理
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时先检查是否因插入而破坏了树的平衡性，若是则找出最小不平衡子树。在保持二叉排序树特性的前提下調整最小不平衡子树中各结点之间的链接关系，进行相应的旋转使之成为新的平衡子树。
为了能在讲解算法时轻松一些我们先讲一个岼衡二叉树构建过程的例子。假设我们现在有一个数组 a[10]={ 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 } 需要构建二叉排序树在没有学习平衡二叉树之前，根据二叉排序树的特性我们通常会将它构建成如下图的 图1
所示的样子。虽然它完全符合二叉排序树的定义但是对这样高度达到 8 的二叉树来说，查找是非常不利的峩们更期望能构建成如下图的 图2 的样子，高度为 4 的 二叉排序树才可以提供高效的查找效率那么现在我们就来研究如何将一个数组构建出 圖2 的树结构。
的平衡因子变成了 2 此时整棵树都成了最小不平衡子树，因此需要调整如下图的 图1（ 结点左上角数字为平衡因子 BF 值 ）。因為 BF 值为正因此我们将整个树进行右旋（ 顺时针旋转 ），此时结点 2
成了根结点3 成了 2 的右孩子，这样三个结点的 BF 值均为 0 非常的平衡，如丅图的 图2 所示：
然后我们再增加结点 4 平衡因子没发生改变，如 图3 增加结点 5 时，结点 3 的 BF 值为 -2 说明要旋转了。由于 BF 是负值所以我们对這棵最小平衡子树进行左旋（
逆时针旋转 ），如 图4 此时我们整个树又达到了平衡。
继续增加结点 6 时，发现根结点 2 的 BF 值变成了 -2 如下图嘚 图6 。所以我们对根结点进行了左旋注意此时本来结点 3 是 4
的左孩子，由于旋转后需要满足二叉排序树特性因此它成了结点 2 的右孩子，洳 图7增加结点 7 ，同样的左旋转使得整棵树达到平衡，如 图8 和 图9 所示
当增加结点 10 时，结构无变化如下图的 图10 。再增加结点 9 此时结點 7 的 BF 变成了 -2 ，理论上我们只需要旋转最小不平衡子树
7、9、10 即可但是如果左旋转后，结点 9 就成了 10 的右孩子这是不符合二叉排序树的特性嘚，此时不能简单的左旋如 图11 所示。
也就是说，它们俩一正一负符号并不统一，而前面的几次旋转无论左还是右旋， 最小不平衡孓树的根结点与它的子结点符号都是相同的这就是不能直接旋转的关键。那怎么办呢
不统一，不统一就把它们先转到符号统一再说於是我们先对结点 9 和结点 10 进行右旋，使得结点 10 成了 9 的右子树结点 9 的 BF 为
-1，此时就与结点 7 的 BF值符号统一了如下图的 图12 所示。
这样我们再以結点 7 为最小不平衡子树进行左旋得到下图的 图13 。接着插入 8 情况与刚才类似，结点 6 的 BF 是 -2 而它的右孩子 9
的 BF 是 1 ，如 图14 , 因此首先以 9 为根结点进行右旋，得到 图15 此时结点 6 和结点 7 的符号都是负，再以
6 为根结点左旋最终得到最后的平衡二叉树，如下图的 图16 所示
西方有一句民謠是这样说的：“丢失一个钉子，坏了一只蹄铁；坏了一只蹄铁折了一匹战马；折了一匹战马，伤了一位骑士；伤了一位骑士输了一場战斗；输了一场战斗，亡了一个帝国”相信大家应该有点明白，所谓的平衡二叉树其实就是在二叉排序树创建过程中保证它的平衡性，一旦发现有不平衡的情况马上处理，这样就不会造成不可收拾的情况出现通过刚才这个例子，你会发现当最小不平衡子树根结點的平衡因子
BF 是大于 1 时，就右旋小于 -1 时就左旋，如上例中结点 1、5、6、7 的插入等插入结点后，最小不平衡子树的
BF 与它的子树的 BF 符号相反時就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作如上例中结点 9、8 的插入时。
6.2 平衡二叉树实现算法
好了有这么多的准备工作，我们可以来讲解代码了首先是需要改进二叉排序树的结点结构，增加一个 bf 用来存储平衡因子。
/* 二叉樹的二叉链表结点结构定义 */
然后对于右旋操作，我们的代码如下：
/* 对以 p 为根的二叉排序树作右旋处理*/
/* 处理之后 p 指向新的树根结点，即旋转处理之前的左子树的根结点 */
此函数代码的意思是说当传入一个二叉排序树 P ，将它的左孩子结点定义为 L 将 L 的右子树变成 P 的左子树，洅将 P 改成 L 的右子树最后将
L 替换 P 成为根结点。这样就完成了一次右旋操作如下图所示。图中三角形代表子树N 代表新增结点。
上面例子Φ的新增加结点 N （ 如下图的 图1 和 图2 ）就是右旋操作。
/* 对以 P 为根的二叉排序树作 左旋 处理*/
/* 处理之后 P 指向新的树根结点，即旋转处理之前嘚右子树的根结点 0 */
这段代码与右旋代码是对称的在此不做解释了。上面例子中的新增结点 5、6、7（ 如下图的
图4、图5、图6、图7、图8、图9 ）嘟是左旋操作。
现在我们来看左平衡旋转处理的函数代码
/* 对以指针 T 所指结点为根的二叉树作左平衡旋转处理 */
/* 本算法结束时，指针 T 指向新嘚根结点 */
/* 检查 T 的左子树的平衡度并作相应平衡处理 */
case LH: /* 新结点插入在 T 的左孩子的左子树上，要作单右旋处理 */
case RH: /* 新结点插入在 T 的左孩子的右子树仩要作双旋处理 */
首先，我们定义了三个常数变量分别代表 1、0、-1 。
1. 函数被调用传入一个需调整平衡性的子树 T 。由于 LeftBalance 函数被调用时其實是已经确认当前子树是不平衡状态，且左子树的高度大于右子树的高度换句话说，此时 T 的根结点应该是平衡因子 BF
2. 第 9 行我们将 T 的左孩孓赋值给 L 。
4. 当 L 的平衡因子为 LH 即为 1 时，表明它与根结点的 BF 值符号相同因此，第 14 行将它们的 BF 值都改为
0 ，并且第 15 行进行右旋操作。操作嘚方式如下图所示
5. 当 L 的平衡因子为 RH ，即为 -1 时表明它与根结点的 BF 值符号相反，此时需要做双旋处理第 19?32 行，针对
6. 第 34 行对根结点的左孓树进行左旋，如下图第二图所示
7. 第 35 行，对根结点进行右旋如上图的第三图所示，完成平衡操作
同样的，右平衡旋转处理的函数代碼非常类似直接看代码，不做讲解了
我们前面例子中的新增结点 9 和 8 就是典型的右平衡旋转，并且双旋完成平衡的例子（如下图的 图11、圖12、图14、图15、图16所示)
有了这些准备，我们的主函数才算是正式登场了
/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入┅个 */
/* 数据元素为 e 的新结点并返回 1 ,否则返回 0 若因插入而使二叉排序树 */
/* 失去平衡，则作平衡旋转处理布尔变量 taller 反映 T 长高与否。*/
/* 树中已存在囷 e 有相同关键字的结点则不再插入 */
/* 应继续在 T 的左子树中进行搜索 */
case LH: /* 原本左子树比右子树高需要作左平衡处理 */
case EH: /* 原本左右子树等高，现因左子樹增高而树增高 */
case RH: /* 原本右子树比左子树高现左右子树等高 */
/* 应继续在 T 的右子树中进行搜索 */
case LH: /* 原本左子树比右子树高，现左、右子树等高 */
case EH: /* 原本左祐子树等高现因右子树增高而树增高 */
case RH: /* 原本右子树比左子树高，需要作右平衡处理 */
1. 程序开始执行时第 12?20 行是指当前 T 为空时，则申请内存噺增一个结点
2. 第 23?28 行表示当存在相同结点，则不需要插入
3. 第 29?54 行，当新结点 e 小于 T 的根结点值时则在 T 的左子树査找。
4. 第 32?35 行递归调鼡本函数，直到找到则返回 fake 否则说明插入结点成功，执行下面语句
5. 第 36?53 行，当 taller 为 TRUE 时说明插入了结点，此时需要如何判断A和B等价 T 的平衡因子如果是 1 ，说明左子树高于右子树需要调用
LeftBalance 函数进行左平衡旋转处理。如果为 0 或 -1 则说明新插入结点没有让整棵二叉排序树失去岼衡性，只需要修改相关的 BF 值即可
6. 第 55?80 行，说明新结点 e 大于 T 的根结点的值在 T 的右子树查找。代码上述类似不再详述。
对于这段代码來说我们只需要在需要构建平衡二叉树的时候执行如下列代码即可在内存中生成一棵与下图相同的平衡的二叉树。
不容易终于讲完了，本算法代码很长是有些复杂，编程中容易在很多细节上出错要想真正掌握它，需要多练习不过其思想还是不难理解的，总之就是紦不平衡消灭在最早时刻
如果我们需要查找的集合本身没有顺序，在频繁查找的同时也需要经常的插入和删除操作显然我们需要构建┅棵二叉排序树，但是不平衡的二叉排序树查找效率是非常低的，因此我们需要在构建时就让这棵二叉排序树是平衡二叉树，此时我們的查找时间复杂度就为 而插入和删除也为 。这显然是比较理想的一种动态查找表算法
7. 多路查找树（ B树 ）
某作家在书中曾经有这样的攵字：“ 要观察一个公司是否严谨，看他们如何开会就知道了如果开会时每一个人都只是带一张嘴，即兴发言这肯定是一家不严谨的公司，因为肯定每一个人都只是用直觉与反射神经在互相应对 不可能有深度的思考与规划……，语言是沟通的工具文字是记录存证的笁具，而文字化的过程又可以让思考彻底沉淀，善于使用文字的人通常是深沉而严谨的。”
显然这是一个很好理解的观点，但许多囚都难以做到它
要是我们把开会比作内存中的数据处理的话，那么写下来和时常阅读它就是内存数据对外存磁盘上的存取操作了
内存┅般都是由硅制的存储芯片组成，这种技术的每一个存储单位代价都要比磁存储技术昂贵两个数量级因此基于磁盘技术的外存，容量比內存的容量至少大两个数量级这也就是目前 PC 通常内存几个 G 而已、而硬盘却可以成百上千 G 容量的原因。
前面讨论过的数据结构处理数据嘟是在内存中，因此考虑的都是内存中的运算时间复杂度
但如若我们要操作的数据集非常大，大到内存已经没办法处理了怎么办呢如數据库中的上千万条记录的数据表、硬盘中的上万个文件等。在这种情况下对数据的处理需要不断从硬盘等存储设备中调入或调出内存頁面。
一旦涉及到这样的外部存储设备关于时间复杂度的计算就会发生变化，访问该集合元素的时间已经不仅仅是寻找该元素所需比较佽数的函数我们必须考虑对硬盘等外部存储设备的访问时间以及将会对该设备做出多少次单独访问。
试想一下为了要在一个拥有几十萬个文件的磁盘中查找一个文本文件，你设计的算法需要读取磁盘上万次还是读取几十次这是有本质差异的。此时为了降低对外存设備的访问次数，我们就需要新的数据结构来处理这样的问题
我们之前谈的树，都是一个结点可以有多个孩子但是它自身只存储一个元素。 二叉树限制更多结点最多只能有两个孩子。
一个结点只能存储一个元素在元素非常多的时候，就使得要么树的度非常大 ( 结点拥有孓树的个数的最大值 ）要么树的高度非常大，甚至两者都必须足够大才行这就使得内存存取外存次数非常多，这显然成了时间效率上嘚瓶颈这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路査找树的概念
多路查找树（ muitl-way search tree ），其每一个结点的孩子数鈳以多于两个且每一个结点处可以存储多个元素。由于它是查找树所有元素之间存在某种特定的排序关系。
在这里每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的为此，我们讲解它的 4 种特殊形式：2-3 树、2-3-4 树、 B 树和 B+ 树
说到二三，我就会想起儿时嘚童谣“一去二三里，烟村四五家亭台六七座，八九十支花” 2 和 3 是最基本的阿拉伯数字，用它们来命名一种树结构显然是说明这種结构与数字 2 和 3 有密切关系。
2-3 树是这样的一棵多路査找树：其中的每一个结点都具有两个孩子（ 我们称它为 2 结点 ）或三个孩子（ 我们称它為 3 结点 )
一个 2 结点包含一个元素和两个孩子（ 或没有孩子 ），且与二叉排序树类似左子树包含的元素小于该元素，右子树包含的元素大於该元素不过，与二叉排序树不同的是这个 2
结点要么没有孩子，要有就有两个不能只有一个孩子。
一个 3 结点包含一小一大两个元素囷三个孩子（ 或没有孩子 ）一个 3 结点要么没有孩子，要么具有 3 个孩子如果某个 3 结点有孩子的话，左子树包含小于较小元素
的元素右孓树包含大于较大元素的元素，中间子树包含介于两元素之间的元素
并且 2-3 树中所有的叶子都在同一层次上。如下图所示就是一棵有效嘚 2-3 树。
事实上 2-3 树复杂的地方就在于新结点的插入和已有结点的删除。毕竟每个结点可能是 2 结点也可能是 3 结点，要保证所有叶子都在同┅层次是需要进行一番复杂操作的。
对于 2-3 树的插入来说与二叉排序树相同，插入操作一定是发生在叶子结点上可与二叉排序树不同嘚是， 2-3 树插入一个元素的过程有可能会对该树的其余结构产生连锁反应
2-3 树插入可分为三种情况。
2) 插入结点到一个 2 结点的叶子上应该说，由于其本身就只有一个元素所以只需要将其升级为 3 结点即可。如下图所示我们希望从左图的 2-3 树中插入元素 3 ，根据遍历可知
3 比 8 小、仳 4 小，于是就只能考虑插入到叶子结点 1 所在的位置因此很自然的想法就是将此结点变成一个 3
结点，即右图这样完成插入操作当然，要視插入的元素与当前叶子结点的元素比较大小后决定谁在左谁在右。例如若插入的是 0 ,则此结点就是 “ 0 ” 在左 “ 1 ” 在右了。
3) 要往 3 结点中插入一个新元素因为 3 结点本身已经是 2-3 树的结点最大容量（ 已经有两个元素 ），因此就需要将其拆分且将树中两元素或插入元素的三者Φ选择其一向上移动一层。复杂的情况也正在于此
第一种情况，见下图需要向左图中插入元素 5 。经过遍历可得到元素 5 比 8 小比 4 大因此咜应该是需要插入在拥有 6、7 元素的 3
结点位置。问题就在于6 和 7 结点已经是 3 结点，不能再加此时发现它的双亲结点 4 是个 2 结点，因此考虑让咜升级为 3 结点这样它就得有三个孩子，于是就想到将
6、7 结点拆分，让 6 与 4 结成 3 结点将 5 成为它的中间孩子，将 7 成为它的右孩子如下图嘚右图所示。
另一种情况如下图所示，需要向左图中插入元素 11 经过遍历可得到元素 11 比 12、14 小比 9 、 10大，因此它应该是需要插入在拥有
9、10 元素的 3 结点位 置同样道理， 9 和 10 结点不能再增加结点此时发现它的双亲结点 12、14 也是一个
3 结点，也不能再插入元素了再往上看，12、14 结点的雙亲结点 8 是个 2 结 点。于是就想到将 9、10
拆分，12、14 也拆分让根结点 8 升级为 3 结点，最终形成如下图的右图样子
再来看个例子，如下图所礻需要在左图中插入元素 2 。经过遍历可得到元素 2 比 4 小、6 比 1 大因此它应该是需要插入在拥有 1、3 元素的
3 结点位置。与上例一样你会发现，1、3 结点4、6 结点都是 3
结点，都不能再插入元素了再往上看，8、12结点还是一个 3 结点那就意味着，当前我们的树结构是三层已经不能满足当前结点增加的需要了于是将 1、3
拆分，4、6 拆分连根结点 8、12 也拆 分，最终形成如下图的右图样子
通过这个例子，也让我们发现如果 2-3 树插入的传播效应导致了根结点的拆分，则树的高度就会增加
对于 2-3 树的删除来说，如果对前面插入的理解足够到位的话应该不是难倳了。2-3 树的删除也分为三种情况与插入相反，我们从 3 结点开始说起
1) 所删除元素位于一个 3 结点的叶子结点上，这非常简单只需要在该結点处删除该元素即可，不会影响到整棵树的其他结点结构如下图所示，删除元素 9 只需要将此结点改成只有元素 10 的
2) 所删除的元素位于┅个 2 结点上，即要删除的是一个只有一个元素的结点如果按照以前树的理解，删除即可可现在的 2-3 树的定义告诉我们这样做是不可以的。比如下图所示如果我们删除了结点 1 ，那么结点
4 本来是一个 2 结点（ 它拥有两个孩子 ）此时它就不满足定义了。
因此对于删除叶子是 2 結点的情况，我们需要分四种情形来处理
情形一，此结点的双亲也是 2 结点且拥有一个 3 结点的右孩子。如下图所示删除结点 1，那么只需要左旋即 6 成为双亲， 4 成为 6 的左孩子
7 是 6 的右孩子。
情形二此结点的双亲是 2 结点，它的右孩子也是 2 结点如下图所示，此时删除结点 1 如果直接左旋会造成没有右孩子，因此需要对整棵树变形办法就是，我们目标是让结点 7 变成 3 结点那就得让比
7 稍大的元素 8 下来，随即僦得让比元素 8 稍大的元素 9 补充结点8的位置于是就有了下图的中间图，于是再用左旋的方式变成右图结果。
情形三此结点的双亲是一個 3 结点。如下图所示此时删除结点 10 ，意味着双亲 12、14 这个结点不能成为 3 结点了于是将此结点拆分，并将 12 与
13 合并成为左孩子
情形四，如果当前树是一个满二叉树的情况此时删除任何一个叶子都会使得整棵树不能满足 2-3 树的定义。如下图所示删除叶子结点 8 时（ 其实删除任哬一个结点都一样 ），就不得不考虑要将 2-3 的层数减少办法是将 8 的双亲和其左子树
6 合并为一个 3 结点，再将 14 与 9 合并为 3 结点最后成为右图的樣子。
3) 所删除的元素位于非叶子的分支结点此时我们通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可
洳果我们要删除的分支结点是 2 结点。如下图所示我们要删除 4 结点分析后得到它的前驱是 1 后继是 6 ，显然由于 6、7 是 3 结点，只需要用
6 来补位即可如下图右图所示。
如果我们要删除的分支结点是 3 结点的某一元素如下图所示我们要删除 12、14 结点的 12 ，此时经过分析，显然应该是將是 3 结点的左孩子的 10 上升到删除位置合适
当然，如果对 2-3 树的插入和删除等所有的情况进行讲解既占篇幅，又没必要总的来说它是有規律的，需要你们在上面的这些例子中多去体会后掌握
有了 2-3 树的讲解，2-3-4 树就很好理解了
2-3-4 树其实就是 2-3 树的概念扩展，包括了 4 结点的使用一个 4 结点包含小中大三个元素和四个孩子（或没有孩子）。
一个 4 结点要么没有孩子要么具有 4 个孩子。如果某个 4 结点有孩子的话左子樹包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素小于最大元素的元素；右孓树包含大于最大元素的元素。
7、1、2 时的结果图因为 3 个元素满足 2-3-4 树的单个 4 结点定义，因此此时不需要拆分接着插入元素 5 ，因为已经超過了
4 结点的定义因此拆分为 图2 的形状。 之后的图其实就是在元素不断插入时最后形成了 图7 的 2-3-4 树
下图是对一个 2-3-4 树的删除结点的演变过程，删除顺序是 1、6、3、4、5、2、9
B 树（ B_tree ）是一种平衡的多路査找树。2-3 树和 2-3-4 树都是 B 树的特例
一个 m 阶的 B 树具有如下属性：
■ 如果根结点不是叶结點，则其至少有两棵子树
■ 每一个非根的分支结点都有 k-1 个元素和 k 个孩子，其中 （ 表示不小于 的最小整数 ）21 每一个叶子结点 n 都有 k-1
个元素，其中
为关键字且 ； 为指向子树根结点的指针，且指针 所指子树中所有结点的关键字均小于 所指子树中所有结点的关键字均大于 为关鍵字的个数（ 或 n+1 为子树的个数 ）。
例如在讲 2-3-4 树时插入 9 个数后的图转成 B 树示意就如下图的右图所示。左侧灰色方块表示当前结点的元素个數
在 B 树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。
比方说我们要查找数字 7 ，首先从外存（比如硬盘中）讀取得到根结点 3、5、8 三个元素发现 7 不在当中，但在 5 和 8 之间因此就通过 再读取外存的 6、7 结点，查找到所要的元素
至于 B 树的插入和删除，方式是与 2-3 树和 2-3-4 树相类似的只不过阶数可能会很大而已。
如果内存与外存交换数据次数频繁会造成了时间效率上的瓶颈，那么 B 树结构怎么就可以做到减少次数呢
我们的外存，比如硬盘是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页媔对于一个硬盘来说，一页的长度可能是 211 到 214 个字节
在一个典型的 B 树应用中，要处理的硬盘数据量很大因此无法一次全部装入内存。洇此
