此文已由作者刘超授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验

5. 双数组Trie树

对于字符串来说，还有一种查询效率较高的数据结构，叫做Trie树。

比如我们有一系列的字符串：{bachelor#, bcs#, badge#, baby#, back#, badger#, badness#}，我们之所以每个字符串都加上#，是希望不要一个字符串成为另外一个字符串的前缀。把它们放在Trie树中，如图所示。

在这棵Trie树中，每个节点都包含27个字符。最上面的是根节点，如果字符串的第一个字符是“b”，则“b”的位置就有一个指针指向第二个层次的节点，从这一层的节点开始，下面挂的整棵树，都是以“b”开头的字符串。第二层的节点也是包含27个字符，如果字符串的第二个字符是“c”则“c”的位置也有一个指针指向第三个层次的节点，第三个层次下面挂的整棵树都是以“bc”为前缀的，以此类推，直到碰到“#”，则字符串结束。通过这种数据结构，我们对于字符串的查找速度就和字符串的数量没有关系了，而是字符串有多长，我们就顶多查找多少个节点，而字符串的长度都是有限的，所以查询速度是相当的快。

当然细心的同学也发现了，高速度的代价就是空间占用太大，而且是指数增加的，还是以27为底数的。好在还是英文啊，说破天不过就是26个字母，要是中文可怎么办啊。所以咱们可不能有没有的都列在哪里，出现的字符咱就占用空间，不出现的咱可不浪费。基于这种理念，上面的那棵Trie树就变成了图的样子。

 

图中仅仅保留了已有的字符，并将每个节点变成了一种状态(State)，在没有任何输入的情况下，我们处于根节点的状态，当输入字符“b”后，便到了下一层的状态Sb ，当再输入字符“a”后，就到了再下一层的状态Sba ，所有在Sba 下面挂着的整棵树都是以“ba”作为前缀的。

熟悉编译原理或者形式语言的同学已经发现了，这是一个有限状态机。不熟悉的同学也不要紧，很容易理解，假设有一个门，有两个按钮“开”和“关”，代表用户的输入，门有两种状态，“开着”和“关着”。门的状态根据用户的输入而变化，比如门处于“关着”的状态，用户输入“开”，就转换到“开着”的状态，然后再点“关”，就回到“关着”的状态。当然也可以识别不合法的输入，比如门本来就“开着”，你还猛点“开”这个按钮，门或者报错，或者没有反应。在上面的有限状态机中也是这样的，一开始处于根节点的状态，用户输入“b”，就进入状态Sb，输入“c”，就进入状态Sbc ，再输入“s”，进入状态Sbcs ，最后用户输入“#”，字符串结束，进入状态Sbcs# ，说明字符串“bcs#”在我们的状态机里面是合法的，存在的。如果用户输入“b”之后输入“z”，在状态机中没有对应的状态，所以以“bz”开头的字符串是不存在的。通过我们的这个有限状态机，同样能够起到查询字符串的作用。

其实这个状态机还可以进一步简化。我们发现有的状态是有多个后续状态的，比如Sbac ，根据输入的不同进入不同的后续状态，而有的状态的后续状态是唯一的，比如当用户到达状态Sbach ，此后唯一的合法输入就是“elor#”，所以根本不需要一个个的进入状态Sbache ，Sbachel ，Sbachelo ，Sbachelor ，直到状态Sbachelor# 才发现用户输入是否存在，而是在到达状态Sbach 之后，直接比较剩余的字符串是否是“elor#”就可以了，所以上面的有限状态机可以变成图的样子，所谓的剩余的这些字符串，我们称之为后缀。

 

接下来的任务，就是如何将这个简化了的树形结构更加紧凑的保存起来了。我们在这里要介绍一种不需要占用太多空间的Trie树的数据结构，双数组Trie树。

顾名思义，双数组Trie树就是将上述的树形结构保存在两个数组中，那怎么保存呢？

我们来看上面的这个树形结构，多么像咱们的组织架构图啊，最上面的根节点是总经理，各个中间节点是各部门的经理，最后那些后缀就是咱们的员工了。现在公司要开会了，需要强行把这个树形结构压扁成数组结构，一个挨一个的坐，那最应该要维护的就是上下级的关系。对于总经理，要知道自己的直接下级，以及公司有多少领导干部。对于中层领导，一方面要知道自己的上级在哪里坐，下级在哪里坐；对于基层领导，除了知道上级在哪里坐，还需要知道员工在那里坐。

双数组Trie树就是一个维护上下级关系的一个数据结构。它主要包含两个数组BASE和CHECK，用来保存和维护领导干部之间的关系的，另外还有一个顺序结构TAIL，可以在内存中，也可以在硬盘上，用来安排咱们员工坐的。更形象的说法，两个数组就相当于主席台，而员工只有密密麻麻坐在观众席上了。

BASE和CHECK数组就代表主席台上的座位，如果第i位，BASE[i]和CHECK[i]都为0，说明这个位置是空的，还没有人坐。如果不是空的，说明坐着一位领导干部，BASE[i]数组里面是一个偏移量offset，通过它，可以计算出下属都坐在什么位置，比如领导Sb 有两个下属Sba 和Sbc ，如果领导Sb 坐在第r个位置，则BASE[r]中保存了一个偏移量q(q>=1)，对于下属Sba ，是由Sb 输入“a”到达的，我们将字符“a”编号成一个数字a，则Sba 就应该坐在q+a的位置，同理Sbc 就应该坐在q+c的位置。CHECK[i]数组里面是一个下标，通过它，可以知道自己的领导坐在什么位置，比如刚才讲到的下属Sba ，他坐在q+a的位置，他的领导Sb坐在第r个位置，那么CHECK[q+a]里面等于r，同理CHECK[q+c]里面也应该是r，那BASE[q+a]和BASE[q+c]中保存的什么呢？当然就是Sba 和Sbc 他们的下属的位子了。所以职场中，每个人都同时扮演两种角色，一方面是上司的下属，一方面是下属的上司，所以每个位子i都有两个数字BASE[i]和CHECK[i]，坐在每个位子上的人都应该知道，自己的上司是谁，下属是谁。

对于基层领导稍有不同，因为基层领导的下属就是普通员工了，不坐在双数组主席台上了，而是坐在TAIL观众席上了，所以对于基层领导，如果他坐在第i个位置，则BASE[i]就不是正的了，而是一个负的值p，表示他是基层领导，在双数组主席台上 没有下属了，而|p|则表示基层领导所下属的哪些普通员工在TAIL观众席上的位置。

至于TAIL观众席的结构，就非常简单了，普通员工嘛，别那么多讲究，一个挨一个的做，用$符合进行分割。

根据上述的原理，上面的那颗树保存在双数组里面应该如图，至于这里面的数据如何形成，下面会一步一步详细说明:

 

图中的最下方是对每个字符的编号。从图中我们可以看出，总经理Sᵋ 总是坐在头一把交椅，CHECK[1]=20，主席台总共有20个位子，总经理当然应该对干部的总体情况有所把握。总经理的下属Sb 坐在BASE[1]+b = 1+2=3的位子上，Sb 的上司是总经理，所以CHECK[3]=1，Sb 的下属有两个Sba 和Sbc ，他们的座位BASE[3]+a=6+1=7以及BASE[3]+c=6+3=9，自然CHECK[7]和CHECK[9]都等于3，以此类推。有人可能会困惑为什么BASE[1]是1而BASE[3]是6，不是1也不是5呢？这是在安排座位的过程中逐渐形成的，从下面双数组Trie树的形成过程大家会更详细的了解，在这里就简单说明一下，对于每一个坐在第i个位置的领导，BASE[i]里面都保存下属相对于他的offset，当然每个领导都希望offset越小越好，这样自己的下属也能坐在前面，对于总经理来说，当然他最牛，所以BASE[1]可以取最小值1，因为总经理刚坐下的时候，主席台是空的，他的下属随便坐都可以，对于其他的领导干部就不一定了，如果BASE[i]取1，结果计算后给自己的下属安排位置的时候，发现位置以及被先来的人坐了，所以没办法，只有增加BASE[i]，让自己的下属往后坐坐。对于状态Sbab ，Sbc ，Sbach ，Sback ，Sbadn ，Sbadger ，Sbadge# ，他们的BASE[i]都是负的，所以他们是基层领导，通过BASE[i]里面的值的绝对值，可以找到TAIL观众席中自己的下属，比如Sbab 的BASE值为-17，在TAIL中第17个字符开始是“y#$”，所以连接起来就是“baby#”。当然TAIL中也有一些很奇怪的，比如第20和第22个都只保存了“#$”，这说明了，除了结束符“#”之外，在最后一个字符才与其他的字符串做了区分，第20个就是这样的，“back#”到了字符“k”才和“bachelor#”有所区分(“back#”和“bachelor#”都是以bac为开头的，都归Sbac 领导，必须提拔字符“k”和“h”到主席台，形成状态Sback 和Sbach 来区分两个团队)，既然分开了，就是一个单独的团队，虽然后面只跟了一个“#”，Sback 作为一个小小领导，也需要等上主席台，别拿村长不当干部。其实还有更惨的，对于第13个，就只剩下分隔符“$”，这是因为“badge”完全是另外一个字符串“badger”的前缀，多亏加了个结束符“#”才将两者区分开来，对于“badge#”来讲，到了“#”字符才区分，那么只好也做上主席台，做个光杆司令了。还有一点奇怪的就是，TAIL中为什么有空位置啊，比如位置7,8,9？这是历史原因造成的，因为一开始字符串“bachelor#”刚来的时候，其他的字符串还没来，公司规模较小，就一个团队，不需要那么多层领导，所以就Sb 作为唯一的一个团队的头坐主席台，其他的“achelor#”都坐观众席，所以“achelor#$”总共占了9个位置，后来“bcs#”来了，光是领导Sb 不足以区分这两个字符串团队“bachelor#”和“bcs#”(他们都是以b开头的啊)，所以“achelor#”中的字符“a”和“bcs#”的字符“c”都被提拔为领导岗位，对两个字符串团队以作区分，就形成了状态Sba 和Sbc (从此“bachelor#”可以说我们是以ba开头的，而“bcs#”可以说我们是以bc开头的)，后来“back#” 来了，仅仅字符“ba”以及“bac”都不足以区分“bachelor#”和“back#”，所以，不但“bachelor#”中的字符“c”被提拔成领导岗位，形成状态Sbac ，字符“h”也被提拔，形成状态Sbach ，从而员工就剩下了“elor#”，被提拔了三位，所以位置7,8,9就空下来了，那为什么不让后面的字符跟上呢？一方面，在双数组主席台中，其他团队的下属的位置都已经标好了，这一跟上都要改，比较麻烦，另外一方面，TAIL很可能保存在硬盘文件中的，将文件中的内容移动，也是很低效的事情。

有了上述结构，对字符串进程查询就方便了，一般按照以下的流程进行：

 

//输入: String inputString=”a1 a2 …… an #”转换成为int[] inputCode
boolean doubleArrayTrieSearch(int[] inputCode) {
int r=1;
int h=0;
do {
int t = BASE[r] + inputCode[h];
if(CHECK[t] != r){
//在双数组中找不到相同前缀，说明不存在与这个集合
// a1 a2 …… ah-1 都相同，ah 不同
//座位t上坐的不是你的领导，在这棵树上这个字符串找不到组织
return false;
} else {
//前缀暂且相同，继续找下一层状态
// a1 a2 …… ah 都相同，下个循环比较ah+1
//说明你属于这个大团队，接着看是否属于某一个小团队
r = t;
}
h = h + 1;
} while(BASE[r]>0)
//到这一步双数组中的结构查询完毕，BASE[r]<0，应该从TAIL中查找了
If（h == inputCode.length - 1）{
//如果已经到了结束符#，说明这个字符串所有的字符都在双数组中，是个光杆司令
Return true;
}
Int[] tailCode = getTailCode(-BASE[r]);//从TAIL中拿出后缀
If(compare(tailCode, inputCode, h+1, inputCode.length -1) == 0){
//比较TAIL中的字符串和inputCode中剩下的”ah+1 …… an #”是否相同，相同则存在
Return true;
} else {
Return false;
}
}

接下来，我们就来看看这种微妙的数据结构是如何构造的。其实构造过程说起来很简单，就是一开始整个双数组中只有根节点，然后随着字符串的不断插入而形成。要插入一个新的字符串，首先还是要调用上面的代码进行搜索一下的，如果能够搜索出来，则这个字符串原来就存在，则什么都不做，如果没有搜索出来，就需要进行插入操作。根据上面的搜索程序，搜索不出来分为两种情况，也就是上面的程序中返回False的地方

1) 第一种情况是在双数组中找不到相同的前缀。也即对于输入字符串a1 a2 … ah-1 ah ah+1 … an #，在双数组中，a1 a2 … ah-1 能找到对应的状态S a1 a2… ah-1 ，然而从ah开始，找不到对应的状态S a1 a2 … ah-1 ah，所以需要将S a1 a2 … ah-1 ah作为S a1 a2 … ah-1的下属加入到双数组中，然后将ah+1 … an #作为S a1 a2 … ah-1 ah的员工放到TAIL中。然而加入的时候存在一个问题，就是原来S a1 a2 … ah-1已经有了一些下属，并经过原来排位置，找到了合适的BASE值，通过它能够找到这些下属的座位。这个时候状态S a1 a2 … ah-1 ah来了，当它想要按照BASE[r] + ah=t找到位置的时候，发现CHECK[t]不为0，也即位置让其他先来的人占去了。这个时候有两种选择，一种选择是改变自己的领导S a1 a2 … ah-1的BASE值，使得连同S a1 a2 … ah-1 ah和其他的下属都能够找到空位子坐下，这就需要对自己的领导S a1 a2 … ah-1的原有下属全部迁移。另一种选择就是既然CHECK[t]不为零，说明被别人占了，把这个占了作为的人迁走，我S a1 a2 … ah-1 ah还是坐在这里，要迁走位置t的人可不容易，要先看他的领导的面子，也即根据CHECK[t]=p找到他的领导的位置，迁移位置t的人，需要改变他的领导的BASE[p]，而BASE[p]的改变，必将导致他的领导的原有所有下属都要迁移，另找 位置。那么选择哪一种方式呢？要看哪种方式迁移的人数少，就采取哪种方式。

2) 第二种情况是在双数组中找出的前缀相同，但是从TAIL中取出的后缀和输入不同。也即对于输入字符串a1 a2 … ah-1 ah ah+1 … an #，在双数组中，a1 a2… ah 能找到对应的状态S a1 a2 … ah ，而ah是基层领导，从TAIL中找出基层员工ah+1 ah+2… ah+k b1b2……bm和剩余的字符串ah+1 ah+2… ah+kah+k+1 … an #进行比较，结果虽不相同，但是他们却有共同的前缀ah+1 ah+2… ah+k，为了区分这是两个不同的字符串团队，他们的共同领导ah+1 ah+2… ah+k是要放到双数组中作为中层领导的，而第一个能够区分两个字符串的字符ah+k+2和b1则作为基层领导放到双数组中，两者在TAIL中的基层员工分别是ah+k+2 … an #和b2……bm

下面咱就详细来一步一步看上面那个双数组Trie是如何构造的。

步骤1 初始状态

如图，初始状态，创业伊始，仅有根节点总经理，BASE[1]=1，CHECK[1]=1，TAIL为空。

 

步骤2 加入bachelor#

加入第一个字符串团队bachelor#，第一个字符“b”作为基层领导进入双数组，成为总经理的下属，所以状态Sb的位置为BASE[1]+b = 1 + 2 = 3，CHECK[3]为0，可直接插入，设CHECK[3]=1，后缀achelor#进入TAIL，BASE[3] = -1，表面Sb为基层领导，员工在TAIL中的偏移量为1。如图。

 

步骤3 加入bcs#

加入bcs#，找到状态Sb，是基层领导，从TAIL中读出后缀进行比较，achelor#和cs#，两者没有共同前缀，所以将a和c放入双数组中作为基层领导区分两个字符串团队即可。新加入的两个状态Sba和Sbc都是状态Sb的下属，所以先求BASE[3]=q，先假设q=1，1+a = 1+1=2，1+c=1+3=4，CHECK[2]和CHECK[4]都为0，可以用来放Sba和Sbc，所以BASE[3]=1，CHECK[2]=3，CHECK[4]=3。两个后缀chelor#和s#放入TAIL，基层领导Sba的BASE[2]=-1，指向TAIL中的后缀chelor#，BASE[4]=-10，指向TAIL中的后缀s#。如图所示。

 

步骤4 加入badge#

加入badge#，找到状态Sba，是基层领导，从TAIL中读取后缀chelor#和dge#进行比较，两者没有共同前缀，于是将字符c和d放入双数组作为基层领导来区分两个字符串团队，形成状态Sbac和Sbad，都作为Sba的下属，于是要计算Sba的BASE[2]=q，假设q=1，1+c = 1+3 = 4，1+d = 1+4 = 5，由于CHECK[4]不为零，所以产生冲突，再次假设q=2，2+c = 5，2+d=6，检查CHECK[5]和CHECK[6]都为零，可以放Sbac和Sbad，所以BASE[2]=2，CHECK[5]=2，CHECK[6]=2。两个后缀helor#和ge#放入TAIL，基层领导Sbac的BASE[5]=-1，指向TAIL中的helor#后缀，基层领导Sbad的BASE[6]=-13，指向TAIL中ge#后缀。如图。

 

步骤5 加入baby#

加入baby#，找到状态Sba，有两个下属是Sbac和Sbad，却没有Sbab，要将Sbab加入到双数组中。当前Sba的BASE[2]=2，根据它来安排Sbab的位置，2+b=4，然而CHECK[4]不为零，有冲突，位置以及被占了。有两种选择，一种是改变Sba的BASE[2]的值，造成Sbac，Sbad，Sbab都要移动，另一种是移动第4位的状态Sbc，先要找他的领导Sb，要移动Sbc，需要修改Sb的BASE[3]的值，如果被修改，则状态Sba和Sbc需要移动。权衡两种选择，选择后者。原来BASE[3]=q=1，假设q=2，2+a=3，2+c=5，CHECK[3]不为零，有冲突，再假设q=3，也有冲突，直到假设q=6，6+a=7，6+c=9，CHECK[7]和CHECK[9]都不为零，可以用来放Sba和Sbc，所以BASE[3]=6，Sba从第2个位置移动到第7个位置，Sbc从第4个位置移动到第9个位置，CHECK[7]和CHECK[9]设为3。把别人赶走了，Sbab就放在了第4个位置，CHECK[4]=7。后缀y#进入TAIL，基层领导Sbab的BASE[4]=-17指向TAIL中的后缀y#。如图。

 

步骤6 加入back#

加入back#，找到状态Sbac，是一个基层领导，从TAIL中读取后缀helor#和k#进行比较，两者没有共同前缀，需要将h和k放到双数组中作为基层领导来区分两个字符串团队，成为状态Sbach和Sback，都是Sbac的下属，计算Sbac的BASE[5]=q，假设q=1,1+k=12,1+h=9，由于CHECK[9]不为零，冲突，再假设q=2，2+k=13，2+h=10，CHECK[10]和CHECK[13]都为零，可以用来存放状态Sbach和Sback，所以BASE[5]=2，CHECK[10]=5，CHECK[13]=5。后缀elor#和#进入TAIL，状态Sbach的BASE[10]=-1指向TAIL中的后缀elor#，状态Sback所谓BASE[13]=-20指向TAIL中的后缀#。如图。

 

步骤7 加入badger#

加入badger#，找到状态Sbad，是基层领导，从TAIL中读取后缀ge#和ger#进行比较，两者有相同的前缀ge，所以g和e需要放入双数组作为中层领导，形成状态Sbadg和Sbadge，另外#和r需要放入双数组作为基层领导，来区分两个不同的字符串团队，形成状态Sbadge#和Sbadger。

先放入状态Sbadg，他的领导是Sbad，计算BASE[6]=q，假设q=1，1+g=8，由于CHECK[8]为零不冲突，所以第8个位置可以用来放状态Sbadg，BASE[6]=1，CHECK[8]=6。

然后放状态Sbadge，他的领导是Sbadg，计算BASE[8]=q，假设q=1，1+e=6，由于CHECK[6]不为零，冲突，再假设q=2还是冲突，直到假设q=6，6+e=11，由于CHECK[11]为零，所以不冲突，所以第11个位置可以用来放状态Sbadge，于是BASE[8]=6，CHECK[11]=8。

最后放状态Sbadge#和Sbadger，他们的领导是Sbadge，计算BASE[11]=q，假设q=1，1+r=19，1+#=20，由于CHECK[19]和CHECK[20]都为零，不冲突，所以第19个位置和第20个位置可以用来放状态Sbadger和Sbadge#，于是BASE[11]=1，CHECK[19]=11，CHECK[20]=11。

后缀#和空后缀进入TAIL，基层领导Sbadger的BASE[19]=-22，指向TAIL中的后缀#，基层领导Sbadge#的BASE[20]=-13，指向TAIL中的空后缀。

 

 

步骤8 加入badness#

加入badness#，找到状态Sbad，不是基层领导，有下属Sbadg，所以要将状态Sbadn加入双数组以加入一个新的字符串团队，后缀ess#入TAIL中。

要放置Sbadn，需要看他的领导Sbad的BASE[6]=1，1+n=15，CHECK[15]为零，不冲突，正好第15个位置空着，可以放置状态Sbadn。如图。

 

好了至此为止，大家应该明白如何创建双数组Trie树了吧，在这里还是提醒大家，相似的原理也在Lucene中得到了应用，我们姑且称之有限状态机规则。

双数组Trie树是个优秀的数据结构，但是整个结构需要保存在内存中，如果写入硬盘，则希望不要改变，不然对于冲突的移动不但复杂，而且耗费性能。

6. M路查找树

如果词典非常的大，内存放不下， 就需要保存在硬盘上了，一旦涉及到硬盘，性能便是一个让人头疼的事情，如果还需要这种数据结构能够进行插入和删除，事情将变得更加糟糕。

那么什么样的数据结构，不要设计的那么复杂，以至于要做改变的时候牵一发而动全身，而查询效率还不错的呢？出了O(1)之外，退而求其次的便是O(logN)，说到这里，很多人就会马上想到，二叉树，如图。

 

二叉树确实不错，插入一个节点或者删除一个节点，影响到的只有本节点和父节点，不会影响整棵树的结构，而且查询速度也不错，O(logN)。如果怕因为树不平衡从而影响性能，可以使用平衡二叉树，如AVL或者红黑树。

但是如果我们仔细计算一下，单就二叉树还是有问题的，因为所有的节点都保存在硬盘上，如果我们有100万的数据，那么每次查询需要进行log2N 约为20次磁盘访问，次数还是太多了。这是因为对于二叉树，每个节点保存一个元素，度仅仅为2。如果要提高性能，则需要减少磁盘的访问次数，一个方法就是每个节点多放几个元素，增加度，减少树的高度，所以就有了m路查找树。

M路查找树或者是空树，或者满足下面的性质：

• 每个节点最多有m棵子树，节点的结构为<n, A0, E1, A1, E2, A2, …… , En, An>，其中Ai是指向子树的指针，Ei是数据元素，每个数据元素都有一个关键字Key，当然还有其他的信息Data。

• Ei.Key < Ei+1.Key

• Ai指向的子树的关键字大于Ei.Key，小于Ei+1.Key

• 所有的子树Ai都是m路查找树

比如如图，就是一个三路查找树。

 

概念不难理解，首先要考虑的问题是m取多大，m太小的话，一次查询需要多次读取硬盘，如果m太大，一个节点的读取就需要很长时间，而且内存也有限，所以m的选取应该是的一个节点的大小是缓存单位或者磁盘块的大小，这也是为什么在向树中插入元素的算法中，超过m就一定要进行节点分裂。其次的问题是如何进行查找，比如要找关键字为x的元素，自然是从最顶层节点开始如果在元素中找到Ei.Key==x，则成功，如果元素中没有，则寻找Ei.Key < x < Ei+1.Key，然后根据指针Ai读取子节点查找。最后就是树的平衡性问题，m路搜索树没有规定每个节点中元素的数目，所以有的节点可能是满的，有的可能是空的，如果出现最不好的情况，每个节点都只有一个元素，那么又变成二叉树了，不平衡降低了查询效率，所以需要一些多路平衡树，下面介绍的B树和B+树就是。

M阶的B树是一个m路查找树，它或者是一个空树，或者满足如下的性质：

• 根至少有两个孩子

• 除了根节点之外，所有的节点至少ceil(m/2)个孩子

• 所有的外部节点位于同一层

如图，就是一个4阶B树

 

这里需要讨论几个事情，首先为什么要保证每个节点至少ceil(m/2)个孩子呢？这就是上面我们讨论过的平衡性，为了提高性能，我们可不想花了半天时间从磁盘上读取出一个节点，结果只有少量的元素，我还要费劲去读别的节点，所以这些元素你们怎么就不能紧凑点放在一起呢？这就是为什么在从树中删除元素的算法中，当每个节点的孩子小于ceil(m/2)就进行节点合并。其次，为什么根可以只有两个孩子呢？这是因为一般情况下，根节点中保存的元素是有限的，内存中基本放的下，根节点很多情况下是保存在内存里面的。再者，有关外部节点，对于B树来讲，是没有外部节点的，因为所有的元素都是放在树形结构的内部节点中的，在实践中，指向外部节点的指针一般设为NULL，如果遇到外部节点，就说明查找失败，之所以强调外部节点是和B+树相区别。

对于向B树里面插入一个元素，一般需要先沿着树找元素应该在的位置，如果树的高度为h，则这个过程可能需要读取h次磁盘，然后找到位置后，如果m比较大，一般情况下，直接写入相应的节点就可以了，于是进行了1次写节点操作，总共需要h+1次磁盘操作，而且仅仅影响一个节点，和我们的期望是很接近的。然而如果碰到某个节点满了，则需要进行节点的分裂，否则一个节点过大，超过一个磁盘块或者缓存单位的话，找另一个磁盘块需要硬盘磁头重新定位，而且缓存需要刷新，从而影响性能。

如图，展示了一个3路B树的普通的分裂过程：

 

对于一般的分裂，受到影响的就是本节点和父节点，本节点一个变两个，两个都要写到硬盘中，父节点要加一项。比如图中插入30，首先经过查询，应该插入到b节点，插入后b节点就成了三个元素，四棵子树了，需要分裂，中间的元素20插入到父节点，左侧的元素10和右侧的元素30分别写入单独的节点中，共需要3次磁盘写入，再加上定位阶段的h次磁盘读取，共h+3次磁盘操作。

当然在有的分裂过程中，父节点因为子节点分裂而加入元素后，也需要分裂，更有甚者一直分裂到根节点。比如图中插入60，经过查询，应该插入到c节点，可是插入后就溢出了，需要分裂，中间的元素70插入到父节点，60和80分别写入两个节点，可是父节点插入70后也溢出了，于是还需要分裂，中间的元素40插入新的根节点，20和70分别写入两个节点。在整个过程中，定位需要读取h个节点，除了最顶层，每一层一个节点分裂成两个节点需要2(h-1)次写入，最顶层除了分裂，还需要写入新的根节点，需要3次写入，所以总共需要h+2(h-1)+3次磁盘操作，也即3h+1次。

在m较大的情况下，分裂的情况还是概率相对较小的，尤其是连锁反应的分裂，所以可以证明，插入操作磁盘访问的平均次数约为h+1，至于如何证明，很多数据结构的书上都有。

对于从B树中删除一个元素，同样需要通过查询来定位这个元素，如果元素在叶子节点上，则可以直接删除，如果元素不在叶子节点上，如图中删除节点70，则需要在节点70右面的指针指向的子树的最小值71来替换70，然后考虑删除叶子节点中的元素71即可。

 

当m比较大的时候，一般情况下，将节点中的元素删除后，再将节点写入就可以了，如果删除的元素本来就在叶子节点，则需要磁盘访问h+1次，如果要删除的元素不在叶子节点，则需要磁盘访问h+2次。如果删除完元素后，节点中的元素数目小于ceil(m/2)-1(也即指针的数目小于ceil(m/2))，那就需要调整了，因为每个节点的元素数目过少将会意味着读取磁盘的次数增加。

如图，展示了B树的删除过程：

 

调整的方法一，就是向兄弟节点借。比如要删除元素60，发现节点的元素已经小于1，发现节点e是满的，借一个元素，于是父节点中70进入节点c，节点e中80进入节点f。在这个过程中，定位要删除的元素读取磁盘次数h，读取被借的节点次数1，借元素的节点和被借元素的节点，以及父节点都需要写入磁盘，次数3，共h+4次磁盘操作。

调整的方法二，就是兄弟合并。比如要删除元素70，发现节点e里面也只有1个，没有可借的，于是合并，节点c，节点e，以及父节点中的分割元素80三方合并，成为节点c中有80, 90。结果更不幸的事情发生了，因为合并，分割元素80需要从父节点中需要删除，然而删除80导致父节点也元素不足，需要向兄弟借，结果兄弟节点a也没钱，又要合并了，于是节点a，节点f和父节点中的分割元素40合并，成为节点a中有20,40，删除父节点中的分割元素，父节点是根节点，没有元素剩余了，删除此节点。在一次合并过程中，定位需要读取磁盘h次，读取兄弟节点1次，写合并后的节点1次，最后还要写父节点1次，共h+3次磁盘操作。

从上面可以看出，借比合并需要的磁盘操作次数多，但是借不能连锁反应，而合并可以连锁反应，于是最差的一种情况是，h层，下面h-2层都连锁反应的进行合并，到了最上面的两层根节点和其子节点，变成借。定位需要读取h次，对于除了根节点和根节点的子节点之外其他h-2个层次的合并，都需要读取1次兄弟节点，然后将合并结果写入1次 (需要写父节点的那1次，因为父节点也需要参与他那个层次的合并而不进行磁盘写入) ，共2 (h-2)次磁盘访问，直到根节点的子节点的删除，需要读取兄弟节点1次，借完元素后写兄弟节点1次，写本节点一次，写父节点1次，共4次，所以总共h + 2(h-2) +4 = 3h次磁盘访问。

从上面对B树读写磁盘的分析我们可以看出，B树从原理上来讲，磁盘操作的次数是大约等于树的高度的，然而当为了保持树的平衡性进行分裂，合并的时候，磁盘操作的次数会成倍的增加，这不是我们期望的。而减少分裂，合并出现的概率的方法，就是m取得比较大的值。

然而前面也分析过，m的取值的大小要是的一个节点的大小约为一个磁盘块或者缓存单元。对一个系统来讲，磁盘块和缓存单元的大小是固定的，要增大m，需要减少每个元素的大小。可是元素的大小也不可能减少啊？从上面的分析中，我们可以看出，我们所有的操作都是针对元素的Key来的，与元素其他的信息无关，而Key的大小一般是不会占据整个元素的主要空间的，既然如此，我们为什么在分裂，合并的操作中，读写整个元素呢？比如我们将外部节点利用起来，存放真正的元素，在内部节点的整棵树上，仅仅保存元素的Key，一方面，对于同样大小的节点，仅仅保存key可是使得m更大，另一方面，对于树的各种调整，都是读写Key，读写的数据量大大减少。这就是我们接下来要介绍的B+树。

一棵m阶B+树具有如下的性质：

• 节点分索引节点和数据节点。索引节点相当于B树的内部节点，所有的索引节点组成一棵B树，具有B树的所有的特性。在索引节点中，存放着Key和指针，并不存放具体的元素。数据节点相当与B树的外部节点，B树的外部节点为空，在B+树中被利用了起来，用于存放真正的数据元素，里面包含了Key和元素的其他信息，但是没有指针。

• 整棵索引节点组成的B树仅仅用来查找具有某个Key的数据元素位于哪个外部节点。在索引节点中找到了Key，事情没有结束，要继续找到数据节点，然后将数据节点中的元素读出来，或者二分查找，或者顺序扫描来寻找真正的数据元素。

• M这个阶数仅仅用来控制索引节点部分的度，至于每个数据节点包含多少元素，与m无关。

• 另外有一个链表，将所有的数据节点串起来，可以顺序访问。

如图，所示：

 

从图中我们可以看出，这是一个3阶B+树，而一个外部数据节点最多包含5项。如果插入的数据在数据节点，如果不引起分裂和合并，则索引节点组成的B树就不会变。

如果在71到75的外部节点插入一项76，则引起分裂，71,72,73成为一个数据节点，74,75,76成为一个数据节点，而对于索引节点来讲相当于插入一个Key为74的过程。

如果在41到43的外部节点中删除43，则引起合并，41,42,61,62,63合并成一个节点，对于索引节点来讲，相当于删除Key为60的过程。

11.1—11.15云计算基础服务全场5折起

免费体验云安全(易盾)内容安全、验证码等服务

更多网易技术、产品、运营经验分享请点击。