大话数据结构-8.8 多路查找树(b树) - 高飞网

8.8 多路查找树(b树)

2017-01-12 23:36:11.0

    多路查找树(muitl-way search tree),其每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。

8.8.1 2-3树

    2-3树是:其中的每一个结点都具有两个孩子(称为2结点)或三个孩子(称为3结点)。

    一个2结点包含一个元素和两个孩子(或没有孩子)。注意不能只有一个孩子!

    一个3结点包含一小一大两个元素和三个孩子(或没有孩子)。注意不能有1个或2个孩子。

    并且2-3树中所有的叶子都在同一层上。


1. 2-3树的插入实现

    对于2-3树的插入来说,与二叉排序树相同,插入操作一定是发生在叶子结点上。与二叉树不同的是,2-3树插入一个元素的过程,可能会对该树的其余结点产生连锁反应。

    2-3树插入可分为三种情况。

    1)对于空树,插入一个2结点即可。

    2)插入结点到一个2结点的叶子上。由于其本身就只有一个元素,所以只需要将其升级为3结点即可。注意,因为“3”比“1”大,因此3要在1的右边。

    3)往3结点中插入一个新元素。因为3结点本身已经是2-3树的结点最大容量,因此就需要将期拆分,且将树中插入元素的三者中选择其一向上移动一层叠 。

    第一种情况,如图8-8-4,需要向左图中插入元素5。经过遍历可得到元素5应该插入到6、7元素的3结点位置。问题就在于,6和7结点已经是3结点,不能再加。此时发现它的双亲结点4是个2结点,因此让它升级为3结点,这样它就得有三个孩子,于是就想到,将6、7结点拆分,让6与4结点成3结点,将5成为它的中间孩子,将7成为它的右孩子,如图8-8-4的右图所示。

    另一种情况,如图8-8-5所示,需要向左图中插入元素11。经过遍历可知它应该是需要插入在拥有9、10元素的3结点位置。同样道理,9和10结点不能再增加结点。此时发现它的双亲结点12、14也是一个3结点,也不能再插入元素了。再往上,12、14结点的双亲,结点8是个2结点。于是就想到,将9、10拆分,12、14也拆分,让根结点8升级为3结点,最终形成如图8.-8-5的右图样子。

    再来看个例子,如图8-8-6所示,需要在左图插入元素2。经过遍历可知它应该插入到拥有1、3元素的3结点位置。与上例一样,发现,1、3结点,4、6结点都是3结点,都不能再插入元素了,再往上8、12结点还是个3结点,意味着当前的树结构是三层已经不能满足当前结点增加的需要了。于是1、3拆分,根结点8、12也拆分,最终形成如图8-8-6的右图样子。


    如果2-3树插入的传播效应导致了根结点的拆分,则树的高度就会增加。


2. 2-3树的删除的实现

    1)所删除的元素位于一个3结点的叶子结点上,这非常简单,只需要在该结点处删除该元素即可,不会影响到整棵树的其他结点结构。

    2)所删除的元素位于一个2结点上,即要删除的是一个只有一个元素的结点。如果按照以前树的理解,删除即可,可现在2-3树的定义告诉我们这样做是不可以的。如图8-8-8所示,如果我们删除了结点1,那么结点4本来是一个2结点,此时就不满足定义了。


    因此,对于删除叶子是2结点的情况,需要分四种情况处理。

    情形一,此结点的双亲也是2结点,且拥有一个3结点的右孩子。如图8-8-9所示,删除结点1,只需左旋,即6成为双亲,4成为6的左孩子,7成为6的右孩子。

    情形二,此结点的双亲是2结点,它的右孩子也是2结点。如图8-8-10所示,此时删除结点1,如果直接左旋会造成没有右孩子,因此需要对整棵树变形,办法就是,让结点7变成3结点,就得把稍大的元素8下来,随即就得让比元素8稍大的元素9补充结点8的位置,于是就有了图8-8-10的中间图,于是再用左旋的方式,变成右图的结点。


    情形三,此结点的双亲是 一个3结点。如图8-8-11所示,此时删除结点10,意味着双亲12、14这个结点不能成为3结点了,于是将此结点拆分,并将12与13合成并成为左孩子。

    情形四,如果当前树是一个满二叉树的情况,此时删除任何一个叶子都会使得整棵树不能满足2-3树的定义,就不得不考虑将2-3的层数减少,办法就是将8的双亲和其左子树6合并为一个3结点,再将14与9合并为3结点,最后成为右图的样子。


    3)所删除的元素位于非叶子的分支结点。此时通常将树按中序遍历后得到此元素的前驱或后缀元素,考虑让它来补位即可。

    如果我们要删除的分支结点是2结点。

    如果删除的分支结点是3结点的某一元素。


8.8.2 2-3-4树

    2-3-4树是2-3树的概念扩展,包括了4结点的使用。

8.8.3 B树

    B树(B-tree)是 一种平衡的多跑查找树,2-3树和2-3-4树都是B树的特例。结果最大的孩子数目称为B树的阶(order),因此,2-3-4树是4阶B树。

    一个m阶的B树具有如下属性:

  1. 如果根结点不是叶结点,则其至少有两棵子树。
  2. 每一个非根的分支结点都有k-1个元素和k个孩子,其中「m/2]≤k≤m。每一个叶子结点n都有k-1个元素,其中[m/2]≤k≤m。
  3. 所有叶子结点都位于同一层次。
  4. 所有分支结点包含下列信息数据(n,A0,K1,A1K2A2,...,Kn,An),共中Ki(i=1,2,...,n)为关键字,且Ki<Ki+1;Ai为指向子树根结点的指针,且指针Ai-1所指子树中所有结点的关键字均小于Ki,An所指子树中所有结点的关键字均大于Kn为关键字的个数。

    2-3-4树插入9个数后的图转成B树示意就如图8-8-17右图所示。左侧灰色方块表示当前结点的元素个数。

    在B树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。

    比方说,要查找数字7,首先从外在(如硬盘中)读取得到根结点3、5、8三个元素,发现7不在当中,但在5和8之间,因此就通过A2再读取外存的6、7结点,查找到所要的元素。

    如果内存与外存交换数据次数频繁,会造成时间效率上的瓶颈。而外存(如硬盘)是将所有的信息分割成相等大小的页面,每次硬盘读写的都是一个或多个完整的页面,对于一个硬盘来说,一页的长度可能是211或214个字节。

    在一个典型的B树应用中,要处理的硬盘数据量很大,因此无法一次全部装入内存。因此会对B对进行调整,使得B树的阶数(或结点的元素)与硬盘存储的页碳大小相匹配。比如一棵B树的阶为1001(即1个结点包含1000个关键字),高度为2,它可以存储超过10亿个关键字。只要让根结点持久地保留在内存中,那么在这棵树上,寻找一个关键字至多需要两次的读取即可。

    通过这种方式在有限内存的情况下,每一次硬盘的访问,都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素,所以与二叉树操作不同,它们减少了必须访问结点和数据块的数量,从而提高了性能。可以说,B树的数据结构就是为内外存数据交互准备的。

    在含有n个关键字的B树上查找时,从根结点到关键字结点的路径上涉及的结点数不超过


8.8.4 B+树

    对于树结构来说,可以通过中序遍历来顺序查找树中的元素,这一切都是在内存中进行,在B树结构中,往返于每个结点之间也就意味着,必须得在硬盘的页面之间进行多次访问。如图8-8-18所示,希望遍历B树,假设每个结点都属于硬盘的不同页面,为了中序遍历所有的元素,页面2->页面1->页面3->页面1->页面4->页面1->页面5。而且每次经过结点遍历时,都会对结点中的元素进行一次遍历。


    为了能够解决所有元素遍历等基本问题,在原有B树结点基础上,加了新的元素组织方式,就是这B+树。

    B+树应文件系统所需而出的一种B树的变形树(严格意义上讲,它已经不是树了,因为它违背了每个元素只在该树中出现一次)。而B+树中,出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者中再次列出。另外每一个叶子结点都会保存一个指向后一叶子结点的指针。

    如图8-8-19所示,就是一棵B+树示意图,灰色关键字即是根结点中的关键字在叶子结点两次列出,并且所有叶子结点都链接在一起。


    一棵m阶的B+树和m阶的B树差异在于:

  1. 有n棵子树的结点中包含n个关键字;
  2. 所有的叶子结点包含全部关键字的信息,及指向含这些关键字记录的指针,叶子结点本身依关键字的大小自小而大顺序链接;
  3. 所有分支结点可以看成是索引,结点中仅含有其子树中的最大(或最小)关键字。

    这样的数据结构好处在于:

    如果是要随机查找,就像B树一样;如果是要从小到达顺序查找,就从最左侧的叶子结点出发,不经过分支结点,而是沿着指向下一叶子的指针就可遍历所有的关键字;另外B+树特别适合带有范围的查找。从根结点出发找到第一个范围内的元素,接着再在叶子结点按顺序查找符合范围的所有记录。