data structure

1. B 树及其基本操作

B 树,又称多路平衡查找树,B 树中所有结点的孩子节点数的最大值称为 B 树的阶。通常用 m 表示 。一棵 m 阶 B 树或为空树,或为满足如下特性的 m 叉树:

  1. 树中每个结点至多有 m 棵子树(即至多含有 m-1 个关键字)。

  2. 若根结点不是终端结点,则至少有两棵子树。

  3. 除根结点外的所有非叶结点至少有 (m/2向上取整) 棵子树(即至少含有 m/2向上取整-1 个关键字)。

  4. 所有非叶结点的结构如下

    n P0 K1 P1 K2 P2 ... Kn Pn
    

    其中,Ki(i=1,2,…,n)为结点的关键字,且满足 K1<K2<…<Kn;Pi(i=0,1,…,n)为指向子树根结点的指针,且指针 P(i-1) 所指向子树中所有结点的关键字均小于 Ki,Pi 所指子树中所有结点的关键字均大于 Ki,n(m/2向上取整-1 <= n <= m-1)为结点中关键字的个数。

  5. 所有的叶结点都出现在同一层次上,并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失败结点,实际上这些结点不存在,指向这些结点的指针为空)

B 树是所有结点的平衡因子均等于 0 的多路查找树。

1.1 B 树的高度(磁盘存取次数)

由下一节可知,B 树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。

下面来分析 B 树在不同情况下的高度。当然,首先应该明确 B 树的高度不包括最后的不带任何信息的叶结点所在的那一层。

若 n ≥ 1,则对任意一棵包含 n 个关键字、高度为 h、阶数为 m 的 B 树:

  1. 因为 B 树中每个结点最多有 m 棵子树,m-1 个关键字,所以在一棵高度为 h 的 m 阶 B 树种关键字的个数应满足 n ≤ (m-1)(1 + m + m^2 +... + m^h-1)=m^h-1 ,因此有

    h≥log_m(n+1)

  2. 若让每个结点中的关键字个数达到最少,则容纳同样多关键字的 B 树的高度达到最大。由 B 树的定义:第一层至少有 1 个结点:第二层至少有 2 个结点;除根结点外的每个非终端结点至少有 m/2向上取整 棵子树,则第 3 层至少有 2×(m/2向上取整) 个结点 …… 第 h+1 层至少有 2(m/2向上取整)^(h-1) 个结点,注意到第 h+1 层是不包含任何信息的叶结点。对于关键字个数为 n 的 B 树,叶结点即查找不成功的结点为 n+1 由此有 n+1≥2(m/2向上取整)^(h-1) ,即 h≤log_(m/2向上取整)((n+1)/2)+1

1.2 B 树的查找

在 B 树上进行查找与二叉查找树很相似,只是每个结点都是多个关键字的有序表,在每个结点上所做的不是二路分支决定,而是根据该结点的子树所做的多路分支决定。

B 树的查找包含两个基本操作:

  1. 在 B 树中找结点
  2. 在结点内找关键字

由于 B 树常存储在磁盘上,因此前一个查找操作是在磁盘上进行的,而后一个查找操作是在内存中进行的,即在找到目的结点后,先将结点中的信息读入内存,然后利用顺序查找或折半查找法查找等于 K 的关键字。

在 B 树上查找到某个结点后,先在有序表中进行查找,若找到则查找成功,否则按照对应的指针信息到所指的子树中查找。查找到叶结点时(对应指针为空指针),则说明树中没有对应的关键字,查找失败。

1.3 B 树的插入

与二叉查找树的插入操作相比,B 树的插入操作要复杂得多。在二叉查找树中,仅需查找到需要插入的终端结点的位置。但是,在 B 树中找到插入的位置后,并不能简单地将其添加到终端结点中,因为此时可能会导致整棵树不再满足 B 树定义的要求。将关键字 key 插入 B 树的过程如下:

  1. 定位。利用前述的 B 树查找算法,找到插入该关键字的最低层中的某个非叶结点(注意,B 树中的插入关键字一定插入在最底层中的某个非叶子结点内)。

  2. 插入。在 B 树中,每个非失败结点的关键字个数都在区间 [m/2向上取整-1,m-1] 内。插入后的结点关键字个数小于 m,可以直接插入;插入后检查被插入结点内关键字的个数,当插入后的结点关键字个数大于 m-1 时,必须对结点进行分裂 。

    分裂的方法是:取一个新结点,在插入 key 后的原结点,从中间位置将其中的关键字分为两部分,左部分包含的关键字放到原结点中,右部分包含的关键字放到新结点中,中间位置 (m/2向上取整) 的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限,则继续进行这种分裂操作,直至这个过程传到根结点为止,进而导致 B 树高度增 1 。

1.4 B 树的删除

B 树的删除操作与插入操作类似,但要稍微复杂一些,即要使得删除后的结点中的关键字个数 ≥ m/2上取整-1,因此要涉及结点的 “合并” 问题。

当所删除的关键字 k 不在终端结点(最底层非叶结点)中时,有下列几种情况 。

  1. 若小于 k 的子树中关键字个数 > m/2上取整-1,则找到 k 的前驱值 k’ ,并用 k’ 来代替 k,再递归地删除 k’ 即可 。
  2. 若大于 k 的子树中关键字个数 > m/2上取整-1,则找到 k 的后继值 k’ ,并用 k’ 来取代 k,再递归地删除 k’ 即可。
  3. 若前后两个子树中的关键字个数均为 m/2上取整-1 ,则直接将两个子结点合并,直接删除 k 即可。

当被删除的关键字在终端结点(最底层非叶结点)中时,有下列几种情况:

  1. 直接删除关键字。若被删除关键字所在结点的关键字个数 > m/2上取整-1 ,表明删除该关键字后仍满足 B 树的定义,则直接删去该关键字。

  2. 兄弟够借。若被删除关键字所在结点删除前的关键字个数 = m/2上取整-1 ,且与此结点相邻的右(左)结点的关键字个数 ≥ m/2上取整 ,则需要调整该结点、右(左)兄弟结点及其双亲结点(父子换位法),以达到新的平衡。

  3. 兄弟不够借。若被删除关键字所在结点删除前的关键字个数 = m/2上取整-1 ,且此时与该结点相邻的右(左)兄弟结点的关键字个数 = m/2上取整-1 ,则将关键字删除后与右(左)兄弟结点及双亲结点中的关键字进行合并

    在合并过程中,双亲结点中的关键字个数会减少。若其双亲结点是根结点且关键字个数减少至 0(根结点关键字个数为 1 时,有两棵子树),则直接将根结点删除,合并后的新结点成为根;若双亲结点不是根结点,且关键字个数减少到 m/2上取整-2 ,则又要与它自己的兄弟结点进行调整或合并操作,并重复上述步骤,直至符合 B 树的要求为止。

2. B+ 树的基本概念

B+ 树是应数据库所需而出现的一种 B 树的变形树。

一棵 m 阶的 B+ 树需满足下列条件:

  1. 每个分支结点最多有 m 棵子树(子结点)。
  2. 非叶根结点至少有两棵子树,其他每个分支结点至少有 m/2上取整 棵子树。
  3. 结点的子树个数与关键字个数相等。
  4. 所有叶结点包含全部关键字及指向相应记录的指针,叶结点中将关键字按大小顺序排列,并且相邻叶结点按大小顺序相互链接起来。
  5. 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。

m 阶的 B+ 树与 m 阶的 B 树的主要差异如下:

  1. 在 B+ 树中,具有 n 个关键字的结点只含有 n 棵子树,即每个关键字对应一棵子树;而在 B 树中,具有 n 个关键字的结点含有 n+1 棵子树。
  2. 在 B+ 树中,每个结点(非根内部结点)的关键字个数 n 的范围是 m/2上取整≤n≤m (根结点 1≤n≤m);在 B 树中,每个结点(非根内部结点)的关键字个数 n 的范围是 m/2上取整-1≤n≤m-1 (根结点:1≤n≤m-1)
  3. 在 B+ 树中,叶结点包含信息,所有非叶结点仅起索引作用,非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。
  4. 在 B+ 树中,叶结点包含了全部关键字,即在非叶结点中出现的关键字也会出现在叶结点中;而在 B 树中,叶结点包含的关键字和其他结点包含的关键字是不重复的。

B+ 树中,分支结点的某个关键字是其子树中最大关键字的副本。通常在 B+ 树中有两个头指针:一个指向根结点,另一个指向关键字最小的叶结点。因此,可以对 B+ 树进行两种查找运算:一种是从最小关键字开始的顺序查找,另一种是从根结点开始的多路查找。

B+ 树的查找、插入和删除操作和 B 树的基本类似。只是在查找过程中,非叶结点的关键字等于给定值时并不终止,而是继续向下查找,直到叶结点上的该关键字为止。所以,在 B+ 树中查找时,无论查找成功与否,每次查找都是一条从根结点到叶结点的路径。