B-tree

zheolong bio photo By zheolong Comment View My Stats

B - tree

B树相当于二叉查找树从两子节点到多子节点的推广和泛化。相对于自平衡二叉查找树，B树是针对读写大块数据的系统进行了优化的，更适合于外部存储器，常用语数据库和文件系统。

概述

在B树中，内部（非叶子）节点具有预定范围内可变数量的子节点。当对节点插入或删除数据时，会改变其子节点个数。为了满足预定的范围，内部节点会合并或分裂。因为允许一定范围的子节点，B树无需像其他自平衡查找树一样频繁进行自平衡，但是会浪费一些空间，因为节点并非全部存满数据。在特定的实现中，子节点数量的下限和上限通常是固定的。例如，在2-3 B树中（通常简称为2-3树），每个内部节点只有2或3个子节点。

B树的每个内部节点会包含若干key。key用于分开其子树。例如，如果内部节点有3个子节点（或子树），那么它就必须有2个key：a1和a2。左子树所有节点的key小于a1，中间子树所有节点的key介于a1和a2之间，右子树所有节点的key大于a2。

通常，key的数量在d和2d之间，d是key的最小数量，d+1是树的最小度或分支因子，实际上，key占用了节点中的大部分空间。因子2保证节点可以分裂或合并。如果内部节点具有2d个key，那么向其增加一个key，可以通过将此2d个key的节点分裂为两个d个key的节点，将新的key加入父节点。分裂后的每个节点中的key数量满足要求的最小key数量。类似，如果一个节点与其相邻节点都有d个key，那么可以删除节点中的一个key，然后让此d-1个key的节点与其相邻的d个key的节点合并，再加上从父节点取下来的一个key，组成新的2d个key的节点。

节点的分支个数（子节点数）比其所存的key多一个。在2-3树中，内部节点可以存一个key（两个子节点）或两个key（三个子节点）。通常使用(d+1)-(2d+1)或最高分支度(2d+1)来表示B树。

B树通过保持所有叶子节点在同一深度来保持平衡。随着新的key加入，深度会缓慢增加，但是整体深度很少增加，而且整体深度增加的结果是所有叶子节点都远离根节点一个深度。

对于查找节点数据所用时间远大于处理数据所用时间时，B树相对于其他可替代方案具有明显的优势。所以其适用于外存储器，例如磁盘。通过最大化每个内部节点的key数量，树的高度降低，减少了耗时数据访问的次数。此外，树的重新平衡很少发生。子节点的数量上限，取决于每个子节点存储的必要信息、磁盘块大小。虽然2-3树很容易解释，但是利用外存储器的实用B树需要大量的子节点以提高性能。

变种

通常的B树仅在内部节点存储key，在叶子节点不存储key。B树包括一些变种，例如B+树和B*树。

  • 在B+树中，内部节点存储的是key的副本；key和record都记录在叶子节点；此外，叶子节点会包括指向下一个叶子节点的指针以加速顺序访问（遍历、范围查找等）。
  • B*树对更多的相邻内部节点进行平衡，以保持内部节点更紧凑。此变种要求非root节点至少2/3的空间被占用，而非1/2。为了保持，在节点满时并非立即分裂节点，而是将其key分给其他相邻节点。当两个节点都满了，则分裂为三个节点。节点的删除比插入更复杂。
  • B树可以变成顺序统计树，以key的顺序搜索第N条记录，或者统计两条记录之间的记录个数，或者其他操作。

技术说明

术语

不幸的是，有关B树的定义在不同的文献中有差异(Folk & Zoellick 1992, p. 362). Bayer & McCreight (1972), Comer (1979), 以及其他人将B树的阶定义为非根节点的key的最小数量。Folk & Zoellick (1992)指出这个定义有歧义，因为不知道key的最大数量。3阶的B树可能包含6个或7个key。Knuth (1998, p. 483) 解决了这个问题，将B树的阶定义为子树的最大数量（即key的最大数量加1）。

术语“叶子”也不统一。Bayer & McCreight (1972)将叶子层定义为包含key的最低层，但是Knuth将叶子层定义为包含key的那一层的下一层(Folk & Zoellick 1992, p. 363)。存在很多可能的实现。在有些实现中，叶子节点包含了所有数据记录；而在其他的实现中，叶子节点可能只包含了指向数据记录的指针。这些选择与B树本身的核心思想无关。

也有一些不幸的选择，比如用k表示子树的个数，而“k”与key的个数混淆。

为了简单起见，许多作者假设一个节点中可以保存的key的个数固定。基本假设就是key的个数固定，节点所占空间固定。在实际使用中，必须采用可变数量的key(Folk & Zoellick 1992, p. 379)。

定义

根据Knuth的定义，阶为m的B树满足以下特性：

  1. 每个节点最多有m个子节点。
  2. 每个非叶子节点（除了根节点）至少有m/2（取上整）个子节点。
  3. 如果根节点不是叶子，至少包含两个子节点。
  4. 具有k个子节点的非叶子节点包含k-1个key。
  5. 所有叶子节点在同一层。

算法

查找

插入

所有的插入都开始于叶子节点。要插入一个新的元素，需要先查找到可以插入该元素的叶子节点，然后通过以下步骤进行插入操作：

  1. 如果叶子节点所含元素个数没有达到最大数量，也就是说还有空间用于插入新的元素。那么就将新元素插入到适当的位置，保持整个节点内的元素有序。

  2. 否则，如果叶子节点已经满了，需要将叶子节点平均地一分为二：

    1. 从叶子节点的元素和新元素组成的有序序列中取出中位元素。
    2. 小于中位元素的元素被放入新的左节点，大于中位元素的元素被放入新的右节点，中位元素可以看作用于分隔二者的元素。
    3. 分隔元素被插入到父节点，如果父节点已经满了，也会一分为二 … 。如果没有父节点（即，节点已经是根节点了），那么就创建一个新的节点作为根节点（增加树的深度）。

如果分裂过程一路向上直达根节点，将会创建一个新的根节点，这个新的根节点具有两个子节点，这就是为什么内部节点与根节点所含最少元素个数不同。每个节点的最大元素个数是U-1。当节点分裂时，一个元素移到父节点，但是也加入了一个新元素。所以必须保证节点的最大元素个数U-1能够分裂成两个合法的节点。如果这个数字是奇数，那么U=2L，分裂出来的其中一个节点包含(U−1)/2 = L - 1个元素，因此是一个合法节点，另一个节点包含L个元素，因此也是合法的。如果U-1是偶数，那么U=2L-1，那么就有2L-2个元素。平分一下就是L-1个元素，即每个节点允许的最少元素个数。

一种改进的算法，可以自上而下进行插入操作，将此过程中遇到的每个满的节点都一分为二。这防止了将父节点再次载入内存，如果节点是在外存储器中这种重新载入内存的操作是很耗时的。然而，为了使用这种改进的算法，必须将一个元素送入父节点，将剩余的U-2个元素分裂为两个合法的节点，而无需添加新元素，这就需要U=2L，而非U=2L-1，很多规范里在B树的定义中会考虑这一点。

删除

对于B树的元素删除，存在两种流行的策略。

  1. 定位并删除相应的元素，然后调整B树，使之符合B树的定义，或者
  2. 从上往下，在进入（访问）一个节点之前，调整B树，使得即使后面遇到元素删除，也可以直接删除而无需任何额外的调整。

下面的算法使用第一种策略。

在删除一个元素时，需要考虑两种特殊情况。

  1. 内部节点的元素是子节点的分隔。
  2. 删除元素可能导致节点内元素个数和子节点数量低于下限。

从叶子节点删除元素

  1. 查找要删除的元素。
  2. 如果此元素在叶子节点，直接删除。
  3. 如果元素个数下溢，那么需要rebalance，参考“删除后重新平衡”。

从内部节点删除元素

内部节点的每个元素都是两个子树的分隔者，所以我们需要找一个用于替换的分隔者。注意，左子树中的最大元素和右子树中最小元素都符合条件，而且二者均位于叶子节点。算法描述如下：

  1. 选择一个新的分隔者（左子树的最大元素，或者右子树的最小元素），从叶子节点中删除之，用其替代待删除元素。
  2. 上述操作会从叶子节点中删除一个元素。如果导致叶子节点的元素个数不足（比定义中要求的元素个数少），那么就从叶子节点开始rebalance。

删除后重新平衡

重新平衡的过程从叶子节点开始，一路向着根节点而去，直到B树重新平衡。如果删除操作导致节点中元素数量不足，那么必须从其他节点借元素才行。通常，可以从元素个数大于最低限制的兄弟节点借一个元素，这个操作称为“旋转”，如果兄弟节点的元素个数只够自己用（都等于最低限制），那么此节点就需要与一个兄弟节点进行合并。合并操作会使得父节点少一个分隔者，那么父节点的元素个数可能不足，需要重新平衡。合并和平衡操作可能会一直向上到根节点。因为最少元素个数的限制并不适用于根节点，所以根节点元素不足不是问题。重新平衡B树的算法如下：

  • 如果不充分节点的右兄弟节点存在，并且其元素个数高于下限，那么就向左旋转
    1. 将分隔元素从父节点拷贝到不充分节点（分隔元素下移；现在不充分节点的元素个数满足定义了）。
    2. 用右兄弟节点的第一个元素替换分隔元素（右兄弟节点虽然失去了一个元素，但是其元素个数至少仍然满足最低要求）。
    3. 现在的B树重新平衡了。
  • 否则，如果不充分节点的左兄弟节点存在，并且其元素个数高于下限，那么就向右旋转
    1. 将分隔元素从父节点拷贝到不充分节点（分隔元素下移；现在不充分节点的元素个数满足定义了）。
    2. 用左兄弟节点的最后一个元素替换分隔元素（左兄弟节点虽然失去了一个元素，但是其元素个数至少仍然满足最低要求）。
    3. 现在的B树重新平衡了。
  • 否则，如果两个兄弟节点的元素个数都等于下限，那么就与其中一个兄弟节点合并，父节点就少了一个分隔元素。
    1. 将分隔元素拷贝到左节点的后面（左节点可能是不充分节点，也可能是具有最低限制的元素的兄弟节点）。
    2. 将右节点的所有元素移到左节点（现在左节点具有最高限制的元素个数，右节点为空）。
    3. 将分隔元素连同其右子节点从父节点删除（父节点失去一个元素）
      • 如果父节点是根节点并且现在没有元素，那么就释放根节点，将合并的节点作为新的根节点（树的深度减少了）。
      • 否则，如果父节点的元素个数低于下限，那么从父节点开始重新平衡。

注意：重新平衡的操作与B+树不同（例如，旋转操作不同，因为父节点具有key的拷贝），与B*树（例如，三个兄弟节点合并为两个兄弟节点）。

顺序访问

当数据库刚被加载的时候，顺序访问性能很高，但是随着数据量的增大，会导致更多的随机I/O，性能下降。

初始构建过程

在实际的应用中，经常利用B树来存储大量数据并通过B树的操作增减数据。在这种情况下，初始的构建过程不是一个个顺序加入初始集合中的元素，而是从输入中直接创建初始的叶子节点集合，然后根据这些节点创建内部节点。这种B树的构建方法称为bulkloading。刚开始，除了最后一个叶子节点，所有叶子节点都多包含了一个元素，用于构建内部节点。

具体的例子需要用图来解释。暂且忽略，以后再加。

文件系统中

大多数文件系统使用B树（或者其变种）；其他方案不太常见，如可扩展性哈希。

除了用于数据库，B树在文件系统中用于对特定文件某个块进行快速随机访问。基本问题就是将文件块i地址，转化为磁盘块（或者可能是CHS）地址。

有些操作系统在创建文件时允许用户分配文件的最大大小。此文件可以被分为连续的磁盘块。当转为磁盘块时，操作系统只需要将文件块地址加上文件对应的起始磁盘块地址。这种模式很简单，但是文件无法超过大小限制。

其他操作系统允许文件增长。这样磁盘块就不是连续的了，所以逻辑快地址与物理块地址的映射就比较重要了。

MS-DOS，使用简单的File Allocation Table（FAT）。FAT对每个物理块都建立一个对应的记录，每个记录标识了是否被某个文件占用，如果是，那么同一个文件的下一个物理块是哪个。所以，每个文件的分配在表中被表示为一个链表。为了找到文件块i的物理地址，操作系统（或者磁盘设备）必须顺序查找FAT中的文件链表。更糟糕的是，为了查找文件，必须顺序扫描FAT。对于MS-DOS来说，这还不是大问题，因为磁盘和文件数量很小，FAT里记录很少，文件链表也很短。在FAT12文件系统（用于软盘和早期磁盘）中，FAT中的记录数最多4080个，而且FAT可以全部放到内存里。随着磁盘越来越大，FAT越来越不适用。在较大的磁盘上使用FAT，可能查找物理地址需要经过额外的磁盘访问。

TOPS-20（以及可能TENEX）使用0至2层的树，类似于B树。