B树

维基百科,自由的百科全书
跳转至: 导航搜索
B树
型態
時間 1972
作者 Rudolf Bayer, Edward M. McCreight
大O符号
时间复杂度
平均 最差
空間 O(n) O(n)
搜尋 O(log n) O(log n)
插入 O(log n) O(log n)
刪除 O(log n) O(log n)

计算机科学中,B树英语:B-tree)是一种自平衡的,能够保持数据有序。這種資料結構能夠讓查找數據、顺序访问、插入數據及刪除的動作,都在對數時間內完成。B树,概括来说是一个一般化的二元搜尋樹(binary search tree),可以拥有多于2个子节点。与自平衡二叉查找树不同,B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程,从而加快存取速度。B树这种数据结构可以用来描述外部存储。這種資料結構常被應用在数据库文件系统的實作上。

概述[编辑]

B树 (Bayer & McCreight 1972) (order为5) (Knuth 1998).

在B树中,内部(非叶子)节点可以拥有可变数量的子节点(数量范围预先定义好)。当数据被插入或从一个节点中移除,它的子节点数量发生变化。为了维持在预先设定的数量范围内,内部节点可能会被连结或者分离。因为子节点数量有一定的允许范围,所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡,但是由于节点没有被完全填充,可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如,在一个2-3 B树(通常简称2-3树),每一个内部节点只能有2或3个子节点。

B树中每一个内部节点会包含一定数量的键值。通常,键值的数量被选定在之间。在实际中,键值占用了节点中大部分的空间。因数2将保证节点可以被拆分或组合。如果一个内部节点有个键值,那么添加一个键值给此节点的过程,将会拆分键值为2个键值的节点,并把此键值添加给父节点。每一个拆分的节点需要最小数目的键值。相似地,如果一个内部节点和他的邻居两者都有个键值,那么将通过它与邻居的合并来删除一个键值。删除此键值将导致此节点拥有个键值;与邻居的合并则加上个键值,再加上从邻居节点的父节点移来的一个键值。结果为完全填充的个键值。

一个节点的分支(或子节点)的数量会比存储在节点内部键值的数量大1。在2-3 B树中,内部节点将会存储1个键值(带有2个子节点)或2个键值(带有3个子节点)。一个B树有时会被描述为或简单地使用最高分支

一个B树通过约束所有叶子节点在相同深度来保持平衡。深度在元素添加至树的过程中缓慢增长,而整体深度极少地增长,并导致所有叶子节点与根节点距离加1。

在节点存取时间远超过里层节点存取时间的条件下,B树在可行的实现中很多优势,因为如此存取节点的开销被分摊到里层节点的多次操作上。这通常出现在当节点存储在二级存储器如硬盘存储器上。通过最大化内部里层节点的子节点的数量,树的高度减小,存取节点的开销被缩减。另外,重新平衡树的动作也更少出现。子节点的最大数量取决于,每个子节点必需存储的信息量,和完整磁盘块的大小或者二次存储器中类似的容量。虽然2-3 树更易于解释,实际运用中,B树使用二级存储器,需要要大量数目的子节点来提升效率。

变体[编辑]

术语B树可以指一个特定的方案,也可以指大体上一类方案。狭义上,一个B树在它内部节点中存储键值,但不需在叶子节点上存储这些键值的记录。大体上的一类包含一些变体,如B+树B*树

在B+树,这些键值的拷贝被存储在内部节点;键值和记录存储在叶子节点;另外,一个叶子节点可以包含一个指针,指向另一个叶子节点以加速顺序存取。

B*树分支出更多的内部邻居节点以保持内部节点更密集地填充。此变体要求非根节点至少2/3填充,而不是1/2。为了维持这样的结构,当一个节点填满之后将不会再立即分割节点,而是将它的键值与下一个节点共享。当两个节点都填满之后,分割成3个节点。

计数B树存储,每一树都带有一个指针和其指向子树的节点数目。这就允许了以键值为序快速查找第N笔记录,或是统计2笔记录之间的记录数目,还有其他很多相关的操作。

名字取义[编辑]

Rudolf BayerEd McCreight 于1972年,在Boeing Research Labs 工作时发明了B 树,但是他们没有解释B 代表什么意义(如果有的话)。Douglas Comer 解释说: 两位作者从来都没解释过B树的原始意义。正如我们所见,“balanced”, “broad” 或 “bushy” 可能适合。其他人建议字母“B”代表 Boeing。源自于他的赞助,不过,看起来把B树当作“Bayer”树更合适些

Donald Knuth 在他1980年5月发表的题为“CS144C classroom lecture about disk storage and B-trees”的论文中推测了B树的名字取义,提出“B”可能意味Boeing 或者Bayer 的名字。

数据库的问题[编辑]

已排序文件的查找时间[编辑]

通常,排序和查找算法会被通过大O符号,刻画为比较级别的数值。对一个有N笔记录的已排序表进行二叉查找,打个比方说,可以在O(log2N)比较级完成。如果表有1,000,000笔记录,那么定位其中一笔记录,将在20 个比较级内完成。 log21,000,000 = 19.931...

大数据库一直以来被存储在磁盘。从磁盘上读取一笔记录,与之后的比较键值操作相比,在花费的运行时间上前者处于支配地位。从磁盘读取记录的时间涉及到一个 寻道时间 和 旋转延迟。寻道时间可能是从0到20或者更多毫秒,旋转延迟平均下来约是旋转周期的一半。对于一个7200 转每分钟的磁盘,旋转周期大约是8.33毫秒。像希捷ST3500320NS这样的磁盘,磁道至磁道的寻道时间为 0.8毫秒,平均读取寻道时间为8.5毫秒。为了简化,假设从磁盘读取花费10毫秒。

乐观来说,如此,在一百万中定位一笔记录将会话花费20次磁盘读取乘上10毫秒每次读取时间,总共是0.2秒。

时间花费没有那么糟糕的原因是,独立的记录被成组地记录在磁盘块上。一个磁盘块可能为16 千字节。如果每笔记录大小为160 字节,那么一个块可以存储100 笔记录。上面假设的磁盘读取时间确切地说是读取一个完整块的时间。一旦磁头到达位置,一个或者更多的磁盘块可以以较小的延迟来完成读取。对于100笔记录每块,最后差不多6个比较级是不需要任何磁盘读取的————都在上次读取操作中完成了。

为进一步加速查找,开始的13或14个比较级(每个需要一次磁盘访问)必须要提速。

提升查找的索引[编辑]

较大程度上的提升是通过索引来做到的。在上面的例子中,初始磁盘读取从2个因素限制了查找范围。这基本上可以通过创建一个辅助索引来改善,这个索引包含每块磁盘块上的首笔记录(有时称为稀疏索引)。这个辅助索引可能只有原始数据库的1%大小,但是它可以更快速地被检索。在辅助索引中查找入口可以告诉我们在主数据库中要读去哪一块;查找辅助索引之后,我们只需要读取主数据库中的特定的某一个磁盘分块————通过一次磁盘读取开销。索引可以提供10,000入口,所以,这样最多需要14个比较级。就像主数据库,辅助索引中最后6个左右的比较级可能在相同的磁盘分块上。索引可以在大约8次磁盘读取中完成查找,目标记录会在9次磁盘读取后获得。

创建辅助索引的窍门是可以重复地给辅助索引创建辅助索引。那样可以实现一个只拥有100 入口,能填满一整个磁盘块的辅助-辅助索引。

要找到想要的记录,我们只需要读取3次磁盘分块,而不是14次。读取和查找辅助-辅助索引中第一个(而且是唯一的)块,标记了相应的辅助索引中的分块。读取和查找辅助索引的分块,标记了主数据库中相应的分块。我们只需要30毫秒,而不是150毫秒就能获取记录。

辅助的索引,使得查找问题从约为log2N 磁盘读取开销的二分查找,变成logbN 磁盘读取开销的查找,其中b为分块因素(每分块的入口数目:b = 100 入口每分块;logb1,000,000 = 3 次读取)。

在实际中,如果主数据库被频繁查找,辅助-辅助索引和大部分的辅助索引可能会存储在磁盘缓存中,所以它们不会产生磁盘读取。

插入和删除带来的麻烦[编辑]

如果数据库不会改变,那么编制索引就很简单,而且索引永远不需要改变。如果他们会改变,那么管理数据库及其索引就变得非常麻烦。

从数据库中删除记录不会引起太大问题。索引可以保持不变,记录只需要标记为已删除。数据库仍然保持有序状态。如果会有很多删除,之后查找和存储就不再那么高效了。

在一个有序文件中进行插入将是个灾难,因为需要给插入的记录制造空间。在文件中第一笔记录后插入记录需要把所有记录向后偏移一个位置。如此的操作在实际中实在太过昂贵。

一种做法是预留一些空间给插入操作。磁盘块有一些空闲空间允许后来的插入,而不是高密度地填充。这些记录可以被标记为像是已删除的记录。

现在,只要块中存在空间,插入和删除都可以很快速。如果一个插入操作在一个块上找不到合适的空间,就在临近的块中寻找,且要调整辅助索引。期望是临近存在足够的空间,以免重新调整大量的块。作为可选方案,可以使用一些非排序的块。

B树运用的理念[编辑]

B树使用了以上所有的想法。特别是:

  • 保持键值有序,以顺序遍历
  • 使用层次化的索引来最小化磁盘读取
  • 使用不完全填充的块来加速插入和删除
  • 通过优雅的遍历算法来保持索引平衡

另外,B树通过保证内部节点至少半满来最小化空间浪费。一棵B树可以处理任意数目的插入和删除。

相关条目[编辑]

B+树