+Wiki
指标 | 平均 | 最差 |
---|---|---|
空间 | \(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树是在波音研究室中被发明出来的,目的是为了有效管理大型随机访问文件的索引页。基本的假设是,索引的数量非常大,以至于只有小块的树可以放在主内存中。相关论文Organization and maintenance of large ordered indices。作者从未解释过 B
代表什么。“你越是思考B树中的B是什么意思,你就能越理解B树”。
定义
根据定义,一个阶数为 m
的B树具有以下属性:
- 每个节点最多有 m 个子节点(子树)
- 除了根节点外,每个非叶子节点最少有 m/2 个子节点(子树)
- 根节点至少有 2 个子节点(子树)(除非B树只有一个节点)
- 一个有 k 个子节点的非叶子节点包含 k-1 个键
- 所有叶子节点都在同一层级,且不携带任何信息
每个内部节点的键作为分隔值划分其子树。例如一个内部节点有 3 个子节点(或子树),那么它必须有两个键:\(a_1\) 和 \(a_2\)。最左边的子树中所有值都小于 \(a_1\),中间的子树中所有值都介于 \(a_1\) 和 \(a_2\) 之间,右边的子树中所有值都大于 \(a_2\)。
- 内部节点
- 内部节点是除叶子节点和根节点以外的所有节点。它的结构通常包含一个有序的元素集合,和子节点指针。每个内部节点最多包含 U 个子女,最少包含 L 个子女。因此,元素的数量总是比子指针的数量少1(元素的数量在 L-1 和 U-1 之间)。U 必须是 2L 或 2L-1 ;因此每个内部节点至少有一半是满的。U 和 L 之间的关系意味着两个半满的节点可以被连接成一个合法的节点,一个满的节点可以被分割成两个合法的节点(需要将一个元素推送到父节点上,如果父节点没有空间则向上递归)。这些属性使我们有可能在 B 树中删除和插入新的数值时以较小的成本调整树以保留 B 树的属性。
- 根节点
- 根节点的子节点数量有和内部节点一样的上限,但没有下限。
- 叶子节点
- 叶子节点不携带任何信息。比叶子高一级的内部节点只存储键(最多是m-1,如果不是根至少是m/2-1)和指向不携带任何信息的节点的指针。
一个深度为 n+1 的B树可以容纳大约 U 倍于深度为 n 的B树的项目,但是搜索、插入和删除操作的成本会随着树的深度增长。与任何平衡树一样,成本的增长比元素的数量要慢得多。有些平衡树只在叶子节点上存储数值,并且叶子节点和内部节点使用两种类型。而B树在树中的每一个节点上都保留数值,除了叶子节点。
B树会有一些不同的定义,比如B树的阶
有的定义为内部节点可存储的最少键值的数量;有些地方定义为内部节点可存储的最大子节点数量。还有在一些设计中,叶子可以保存整个数据记录;而在其他设计叶子可能只保存数据记录的指针。
描述
由于在B树的定义中,允许内部节点的子节点数量维持在 L 到 U 之间的一个范围,这样虽然预留的存储键的空间可能会浪费,但是换来的是不需要像其他自平衡搜索树一样频繁的进行重平衡。子节点数量的下限和上限 LU 在一些特定的B树实现上是固定的。例如2-3树
中,内部阶段的子节点数量只能有 2或3 个。在这弹性的子节点空间内,当发生数据的插入或删除时,如果达到了下限或上限,内部节点可以被 连接 或 分割 以进行重平衡。
当访问一个节点的数据的时间大大超过处理该数据的时间时,B树比其他的实现方式有很大的优势,因为这时访问节点的成本可以通过节点内的多个操作来摊销。这通常发生在节点数据在二级存储中,如磁盘驱动器。通过最大限度地增加每个内部节点内的键的数量,树的高度减少了,昂贵的节点访问的数量也减少了。此外,树的重新平衡发生的频率也较低。子节点的最大数量取决于每个子节点必须存储的信息和一个完整磁盘块的大小或二级存储中的类似大小。虽然 2-3B型树 更容易理解,但使用二级存储的实用B型树通常需要大量的子节点来提高性能。
B树在数据库中的应用
做排序后磁盘数据中进行搜索的速度
通常情况下,一个平衡二叉树的搜索时间复杂度为 \(O(log_2 N)\)。大型数据库的数据都是保存在磁盘驱动器上。因此每次读取磁盘都需要发生磁盘IO操作,需要0-20ms的寻道时间和大约8ms的旋转。因此从一百万记录中找出一条数据需要20次磁盘IO,每次算10ms,就需要200ms的时间。
但是,数据库的实现一般会按数据块来存储数据,一次IO可以读取一整个数据块,一个数据块可以存储多条记录。数据块大小通常是16kb。然后因为最后6次左右的搜索比较操作,一般都可以在同一个数据块的数据内完成。因此对于一百万条记录中进行搜索,20次的磁盘IO,性能损耗一般是在前14次比较操作。
索引对搜索效率的提高
B树索引创建了一个多级的树状结构,将数据库分解成固定大小的块或页,这棵树的每一级都可以保存页面的地址来与页面建立连接。允许一个页面(成为节点或内部页面)引用一个树中下一级的一个页面。一个页面通常是树的起点,或称为根节点。这是搜索一个特定键的开始。
B树相比于二叉树,每个节点允许有两个以上的子节点,这样会有更短的高度。在需要进行磁盘读取的时候可以显著的提升性能。
通过对每一个磁盘块中的第一条记录建立辅助索引
(有时又称为稀疏索引
),而不是对每一条记录建立索引,可以将索引的体积减少到 1% 。 这样在进行搜索时,辅助索引会告诉我们目标在哪一页。然后需要额外一次磁盘读写来最终查找到我们的目标。由于一页可以存储10000条记录,所以这种稀疏索引可以把20次比较减少到14次。后6次仍然是在一次页面读取后进行,目标记录所在页面大概在进行8次磁盘读取(索引比较)后定位。这样,使用辅助索引可以把磁盘读写减少到9次(8次读取索引来定位页+1次读取页)。
同时,也可以继续对辅助索引建立另一个辅助索引。这样一个辅助索引的辅助索引
只需要包含100条记录,就可以存储进一个磁盘页。
相比于读取14个磁盘页来搜索目标记录,现在只需要读取3个磁盘页。这种分页就是创建B树的核心思想。磁盘页填充了一个层次结构,构成了索引。读取并对作为辅助索引的辅助索引
根节点的第一个页进行搜索,就可以定位辅助索引
中的相关磁盘页。读取并对该磁盘页进行搜索,就可以确定要读取的目标记录的相关磁盘页。直到最后读取到叶子节点,就可以确定数据库中的一条记录。
辅助索引(稀疏索引)将索引问题从二叉搜索树的需要大约 \(O(log_2 N)\) 次磁盘读取,变成了只需要 \(O(log_b N)\) 次磁盘读取。其中 b
是分页因子。
在实践中,如果数据库经常被搜索,辅助索引的辅助索引
和大部分的辅助索引
可能驻留在磁盘缓存中,所以它们不会产生磁盘读取。B树仍然是几乎绝大多数数据库的标准索引实现。
插入和删除操作
如果数据库中的数据经常变化,那么管理数据库和它的索引就会变的复杂。从数据库中删除数据是相对容易的,可以保持索引不变,只标记记录为删除。但是如果有大量的删除,搜索和存储的效率就会降低。
在一个排序后的文件中进行插入会非常慢。因为要对数据进行移动。因此可以预留一些空间,或使用那些被标记为删除的记录空间。只要插入时不需要进行移动,就会很快。如果插入时当前区块放不下,就必须在附近的区块上寻找空间,这时就需要调整辅助索引。如果附近的区块有足够的空间,就可以避免对大量的区块进行重组。另一种解决方式是直接使用不排序的磁盘区块。
在数据库中使用B树的优点
- B树中的键是有序的,以便于顺序遍历
- 使用分层索引来减少磁盘读取的次数
- 使用预留空间的页来加快插入和删除的速度,减少索引的重排列
- 使用递归算法保持索引树的平衡
- 通过限制内部节点至少有一半是满的来最大限度的减少浪费。
最好和最坏情况下树的高度
设 \(h \ge 0\) 为树的高度。\(m\) 为内部节点的最大子节点数量。\(m/2\) 为内部节点的最少子节点数量。则:
- 最好情况内部节点全满的情况下,树的最小高度为:\(h_{min} = [log_m (n+1)]-1\)
- 最坏情况内部节点全半满的情况下,设\(d=m/2\),树的最大高度为:\(h_{max} = [log_d {n+1 \over 2}]\)
算法
插入
插入操作发生在叶子节点,需要先进行查找,来找到需要插入的位置。插入操作会有两种情况:
- 如果即将被插入的节点当前未满,有足够的空间存放新元素,那么把新元素放入到节点中,并排序。
- 如果即将被插入的节点当前是满的,那么就需要分裂被插入的节点为两个子节点。从当前节点的元素和新元素中找到中间值。所有小于中间值的元素放在左子节点;所有大于中间值的元素放在右子节点;中间值上升到父节点。如果当前父节点也是满的,就递归此操作,直到根节点。如果到根节点时也是满的,只需要把新的中间值当做新的根节点。
但是递归分裂会在查找的链路上进行二次回溯,所以需要的话,另一种方式是在进行查找的过程中预先把满的节点进行分裂。
删除
有两种删除策略:
- 找到并删除元素,然后如果需要,重组树以保持其性质
- 在查找元素的过程中重组树,这样一旦找到要删除的元素就可直接进行删除
在删除一个元素时,有两种情况:
- 从叶子节点删除
- 如果删除会导致节点内元素少于最少数量,需要进行重平衡
- 从内部节点删除
- 由于内部节点的元素作为两颗子树的分隔值,因此需要找一个新的分隔值替代。可选的有左子树最大元素或右子树中的最小元素。由于替代的元素原位置会少一个,如果触发了数量下限,就在替代元素的叶子节点进行重平衡
重平衡
重平衡从叶子节点开始向根部进行,直到树被平衡。如果元素的删除导致节点元素少于最少数量,就需要重新分配一些元素。重新分配有两种方式,一是从相邻兄弟节点移动一个元素,成为旋转。二是与相邻兄弟节点进行合并。合并会导致父节点失去一个元素,此时父节点按需触发重平衡。重平衡算法如下:
- 如果缺陷节点的右边兄弟节点存在,并有足够的元素可以移出,那么就向左旋转
- 将父节点的值复制到缺失节点的末尾
- 用右侧兄弟节点的第一个元素替换父节点中的值
- 如果缺陷节点的左边兄弟节点存在,并且有足够的元素可以移出,那么就向右旋转
- 将父节点的值复制到缺陷节点的头部
- 用左侧兄弟节点的最后一个元素替换父节点中的值
- 如果左右两个兄弟节点都没有足够的元素可以移出,那么就进行合并
- 将父节点的分隔值复制到左节点的末尾
- 将右节点所有元素移动到左节点
- 从父节点删除分隔值和它的空右子节点
- 对父节点按需进行重平衡
B树及空间利用率
在使用一个排序后的数据创建B树时,B树的所有节点都是半满的。如果有需要提高其利用率,可以打乱插入顺序。或使用非均匀的平衡方式,在拆分节点时不是平均的拆分,而是优先以左左子节点满为目标进行拆分。
性能
与链表的线性相比,B树随着数据量的增长而增长得更慢。与跳表相比,这两种结构具有相同的性能,但B树对不断增长的n有更好的扩展性。T树,用于主内存数据库系统,是类似的,但更紧凑。
在文件系统中的应用
除了在数据库中使用外,B树及其各种变体也被用于文件系统中,允许快速随机访问特定文件中的任意块。例如苹果系统的HFS+、微软的NTFS、Linux的Ext4都使用B树
B数的并发访问
并行算法
由于B树的结构与红黑树相似,红黑树的并行算法也可以应用于B树。