搜索引擎的设计(1):词典的设计 下篇

叁叁肆2018-11-09 14:53

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

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

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折起

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

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