数据库索引之B树与B+树

zhyjc6于2020-04-22发布 约6139字·约13分钟 本文总阅读量次

一般的数据结构处理数据都是在内存中处理，由于内存读取速度快，因此计算复杂度的时候就不考虑内存读取速度。而如果要处理的数据量很大，大到内存无法处理，那么数据就只能存放在外设比如磁盘中了。但是磁盘的数据存取速度远远小于内存，这时候我们考虑数据结构以及算法的复杂度就不能忽略磁盘存取时间了。由于有序树的查找、插入、删除的时间复杂度都与树的高度成正比，因此，我们不得不想方设法降低树的高度。

于是就出现了多路查找树（multi-way search tree），其每个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，因此元素之间是有序的。

相对于普通平衡二叉搜索树，多叉搜索树通过进行更大量的计算来换取更少量的磁盘读取次数。

B树

B树（B-tree）是一种平衡的多路查找树

B-树

B-树？指的就是B-tree，这里不读作B减树，因为这里的 “ - ” 是分隔符而不是减号，毕竟英文名称不可能这样写吧：Btree？BTREE？之前我一直还以为有一种树叫做B-树，现在才知道那就是B树，翻译没翻译好真的有点害人。但是真的有B+树。

概述

在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说就是是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

——《维基百科》

由于在大多数系统中，一个B树算法的运行时间主要由它所执行的DISK-READ和DISK-WRITE操作的次数决定，所以我们希望这些操作能够读或写尽可能多的信息。因此，一个B树结点通常和一个完整磁盘页一样大，并且磁盘页的大小限制了一个B树结点可以含有的孩子个数。

对存储在磁盘上的一棵大的B树，通常看到分支因子在50-2000之间，具体取决于一个关键字相对于一页的大小。一个大的分支因子可以大大地降低树的高度以及查找任何一个关键字所需的磁盘存取次数。

——《算法导论》

在B树中，每一个内部节点会包含一定数量的键，键将节点的子树分开，节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量可能会发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能会浪费一些空间。

一个高度为n+1 的 m 阶B树可以容纳的元素数量大约是高度为 n 的B树的 m 倍，但是搜索、插入和删除操作的开销也会增加。和其他的平衡树一样，这一开销增加的速度远远慢于元素数量的增加。

一些平衡树只在叶子节点中存储值（如B+树），而且叶子节点和内部节点使用不同的结构。B树在每一个节点中都存储值，所有的节点有着相同的结构。然而，因为叶子节点没有子节点，所以可以通过使用专门的结构来提高B树的性能。

术语

定义

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

  1. 每一个节点最多有 m 个子节点
  2. 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
  3. 如果根节点不是叶子节点，那么它至少有两个子节点
  4. 有 k 个子节点的非叶子节点拥有 k − 1 个键
  5. 所有的叶子节点都在同一层

操作

查找

B树的搜索和二叉搜索树类似。要查找关键字key，从根节点开始，在该节点中使用顺序查找或二分查找的方法查找key，若找到则查找成功；否则递归进入对应的子树中继续查找；如果当前结点是叶子节点且还没有找到，那么查找失败。

插入

所有的插入都从根节点开始。要插入一个新的元素，首先使用类似于BST搜索的方法找到新元素应该被添加到的对应节点（一个结点可以存储多个值）。将新元素插入到这一节点中的步骤如下：

  1. 如果节点拥有的元素数量小于最大值，那么就说明该结点还有空间容纳新的元素。将新元素插入到这一节点，且保持节点中元素有序即可！
  2. 否则的话说明这一节点已经满了（发生上溢），将它平均地分裂成两个节点：
    1. 从该节点的原有元素和新的元素中选择出中位数，新建左右两个结点
    2. 小于这一中位数的元素放入左边节点，大于这一中位数的元素放入右边节点（子节点根据元素值插入左右结点），中位数作为分隔值。
    3. 分隔值被插入到父节点中，这可能会造成父节点分裂，分裂父节点时可能又会使它的父节点分裂，以此类推。如果没有父节点（这一节点是根节点），就创建一个新的根节点（增加了树的高度）。

如果分裂一直上升到根节点，那么一个新的根节点会被创建，它有一个分隔值和两个子节点。这就是根节点并不像内部节点一样有最少子节点数量限制的原因。

删除

有两种常用的删除策略：

策略一

删除元素其实和AVL树差不多，所有的删除都可以转化为删除叶子结点中的元素的情况。删除叶子结点中的元素很简单，难点在于删除元素后可能出现的再平衡问题。

删除叶子节点中的元素

  1. 搜索要删除的元素
  2. 如果它在叶子节点，将它从中删除
  3. 如果发生了下溢出（元素数量低于最低值），按照后面 “删除后重新平衡” 部分的描述重新调整树

删除内部节点中的元素

内部节点中的每一个元素都作为分隔两颗子树的分隔值，因此我们需要重新划分。值得注意的是左子树中最大的元素仍然小于分隔值。同样的，右子树中最小的元素仍然大于分隔值。这两个元素都在叶子节点中，并且任何一个都可以作为两颗子树的新分隔值。算法的描述如下：

  1. 选择一个新的分隔符（左子树中最大的元素或右子树中最小的元素），将它从叶子节点中移除，替换掉被删除的元素作为新的分隔值。
  2. 前一步删除了一个叶子节点中的元素。如果这个叶子节点拥有的元素数量小于最低要求（发生下溢），那么从这一叶子节点开始重新进行平衡。

删除后的重新平衡

由于删除而需要再次调整平衡，基本可以确定是结点发生了下溢。重新平衡是从叶子节点开始向根节点进行，直到树重新平衡。如果删除节点中的一个元素使该节点的元素数量低于最小值，那么一些元素必须被重新分配。重新平衡树的算法如下：

总的来说就是先找左右兄弟，条件允许就做左旋或右旋就ok；条件不允许，那么只能合并左右兄弟中的一个，可能会回溯到根结点。

策略二

暂无

复杂度

算法 平均 最差
空间 $O(n)$ $O(n)$
搜索 $O(log n)$ $O(log n)$
插入 $O(log n)$ $O(log n)$
删除 $O(log n)$ $O(log n)$

B+树

概述

B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

定义

目前网络上没有B+树的明确定义，特别是结点中元素数量与结点的子树数量之间的关系。目前我了解到的说法有两种：

由于多数人使用说法二的定义，所以这里也使用说法二的定义。那么B+树的定义就仅仅是在B树的定义中增加一些条目了。

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下：

  1. 每个结点至多有m个子女；
  2. 除根结点外，每个结点至少有 ⌈m/2⌉个子女，根结点至少有两个子女；
  3. 有k个子女的结点必有k-1个关键字。
  4. 所有分支结点可以看成索引部分，结点中只包含其直接子树中的最大（最小）关键字。
  5. 所有的叶子结点中包含全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点按关键字大小使用指针顺序链接；

操作

查找

通常在B+树中有两个头指针：一个root指向根结点，另一个head指向包含最小关键字的叶子结点。这决定了B+树有两种查找方式：一种是利用head指针直接从最小关键字开始按顺序查找；另一种是利用 root 指针从根结点开始随机查找，查找方式和 B-树类似，但在查找时，若在非叶子结点上找到等于给定值的关键字，查找并不结束，而是继续向下直到叶子结点（因为只有叶结点中才保存有指向具体数据的指针）。

插入

使用上面的查找方法找到待插入关键值应该插入的叶结点，判断该叶结点中元素是否达到最大容量，如果没有，那么直接插入，插入完成；否则，插入关键值，找出中位数，然后根据中位数将其平均分裂成两个子节点，再将中位数关键字放入分裂前该叶子节点的父结点中。若父节点元素数量超过限制，则继续分裂，如果根节点被分裂，则创建一个新根节点。

删除

通过上面的查找方法找到包含待删除的关键值的叶子节点，如果该叶子节点中元素数量大于最低数量要求，那么直接删除该关键值，删除完成。如果找到该叶子结点并发现其元素数量刚好是最小数量，那么直接删除的话就破坏了结点元素数量的要求了。此时我们需要调用B树的删除后再平衡策略：

重新平衡从叶子节点开始向根节点进行，直到树重新平衡。如果删除节点中的一个元素使该节点的元素数量低于最小值，那么一些元素必须被重新分配。重新平衡树的算法如下：

  • 如果缺少元素节点的右兄弟存在且拥有多余的元素，那么向左旋转
    1. 将父节点的分隔值复制到缺少元素节点的最后（分隔值被复制下来；缺少元素的节点现在有最小数量的元素）
    2. 将父节点的分隔值替换为右兄弟的第一个元素（右兄弟失去了一个节点但仍然拥有最小数量的元素）
    3. 树又重新平衡
  • 否则，如果缺少元素节点的左兄弟存在且拥有多余的元素，那么向右旋转
    1. 将父节点的分隔值复制到缺少元素节点的第一个节点（分隔值被移下来；缺少元素的节点现在有最小数量的元素）
    2. 将父节点的分隔值替换为左兄弟的最后一个元素（左兄弟失去了一个节点但仍然拥有最小数量的元素）
    3. 树又重新平衡
  • 否则，如果它的两个直接兄弟节点都只有最小数量的元素，那么将它与一个直接兄弟节点以及父节点中它们的分隔值合并
    1. 将分隔值复制到左边的节点（左边的节点可以是缺少元素的节点或者拥有最小数量元素的兄弟节点）
    2. 将右边节点中所有的元素移动到左边节点（左边节点现在拥有最大数量的元素，右边节点为空）
    3. 将父节点中的分隔值和空的右子树移除（父节点失去了一个元素）
      • 如果父节点是根节点并且没有元素了，那么释放它并且让合并之后的节点成为新的根节点（树的高度减小）
      • 否则，如果父节点的元素数量小于最小值，重新平衡父节点

总的来说就是先找左右兄弟，条件允许就做左旋或右旋就ok；条件不允许，那么只能合并左右兄弟中的一个，可能会回溯到根结点。

复杂度

算法 平均 最差
空间 $O(n)$ $O(n)$
搜索 $O(log n)$ $O(log n)$
插入 $O(log n)$ $O(log n)$
删除 $O(log n)$ $O(log n)$

B树和B+树的区别

B+树是B树的一种变形。在B树中，每个元素在树中只能出现一次，可能在叶结点上，也可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当作中序遍历的后继结点再次出现在子节点中。因此叶子节点中元素包含了所有分支结点中的元素。另外，每一个叶子节点都会保存一个指向后一个叶子节点的指针。

其它的不同点：

参考资料