(转载)关于B-tree多种定义的分析   Leave a comment

原文出处:http://blog.oldsharp.info/btree_definition/   write by

–在研究OLTP和OLAP系统的时候看到B-tree查询,想多了解一些,然后发现了Rui写的这篇B-tree的研究,觉得很全面,就转载过来。

关于B-tree多种定义的分析

最近我在学习B-tree的过程中遇到了不同文献有不同定义的问题。经过一段时间的思考与调研,我总结了一些自己的想法,于是就有了写作本文的打算。本文将简单介绍索引与B-tree的关系,并试图简要分析历史上B-tree不同定义的本质原因。

开胃菜

做数据库的同学对B-tree一定不会感到陌生。B-tree(中文翻译为B树或者B-树)是我们熟知的一个经典数据结构,它是一种平衡的多路查找 树,广泛应用于计算机文件系统与数据库索引。B-tree的前身最早可以追溯到J. E. Hopcroft于1970年提出的2-3 tree,而它正式登上历史舞台则要归功于R. Bayer和E. McCreight在1972年发表的论文”Organization and Maintenace of Large Ordered Indexes“。

说到B-tree与数据库系统的关联,就不得不提到索引。索引(Index)是数据库系统中的一个重要概念,本质上说,索引是一种为了帮助数据库系 统高效获取数据而由其维护着的满足特定查找算法的数据结构。索引的类型有很多种,如B-tree索引,R-tree索引,Full-Text索 引,Hash索引等,当然本文仅仅关注与讨论B-tree索引。一般来说,实际应用中由于数据库系统维护的数据库文件可能体积非常庞大,对应的索引也就很 大,不可能一次读入主存。因此索引会以索引文件的形式存放在磁盘上。传统磁盘I/O速度相对于主存要慢上若干个数量级(目前情况是5个),所以涉及磁盘的 查找我们必须想办法减少磁盘I/O的次数。

而B-tree就是能够达到这样一种效果的数据结构。我们知道B-tree与一般的平衡树如AVL-TreeRed-Black Tree的 一个显著区别是B-tree的每个内结点可以拥有很多个Children(这个度量被称为内结点出度,下文会更深入的讨论之),那么我们可以在技术上使 B-tree的结点大小为磁盘一个页的大小,并且在新建结点时直接申请一个页大小的空间,使得结点的物理存储位置也是在一个页里,这样就能实现存取一个结 点只需一次磁盘I/O。在最坏情况下,B-tree的一次检索最多需要H(树的高度)次的磁盘I/O,记N为B-tree中的Key的数据量,t为内结点出度的1/2,我们可以证明H ≤ logt(N+1)/2,亦即渐进复杂度为O(H)=O(logtN)。这意味着,一棵拥有200万Key的B-tree,在内结点出度为200时它的树高H最多为3。实际上,为了取得更大的内结点出度,各个数据库一般会采用B-tree的变种如B+-tree,B*-tree来实现索引,比如MySQL的存储引擎InnoDB就采用B+-tree来实现聚簇索引。

如果想更深入的了解索引与B-tree的关系,我这里推荐一篇比较好的文章:《MySQL索引背后的数据结构及算法原理》。

正餐

刚才罗嗦了那么多,我们总结其中的几个要点:
1. B-tree是平衡的多路查找树
2. 涉及到磁盘的查找我们要设法减少磁盘I/O次数
3. B-tree就是为解决这个问题而引入的数据结构。

好了,现在我们来关注B-tree本身。大家最初是如何知晓B-tree这个数据结构的呢?我最早接触B-tree是在大学的数据结构课程,当时的教材是严蔚敏版的《数据结构(C语言版)》(以下简称“严版”)。这本教材中关于B-tree的定义是这样子的:

一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:

  1. 树中每一个结点至多有m棵子树;
  2. 若根结点不是叶子结点,则至少有两棵子树;
  3. 除根结点之外的所有非终端结点至少有⌈m/2⌉棵子树;
  4. 所有的非终端结点中包含下列信息数据(n, A0, k1, A1, k2, A2, …, Kn, An), 其中:Ki(i=1, …, n)为关键字,且Ki < Ki+1(i=1, …, n-1); Ai(i=0, …, n)为子树根结点的指针,且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1, …, n), An所指子树中所有结点的关键字均大于Kn, n(⌈m/2⌉-1 ≤ n ≤ m-1)为关键字的个数(或n+1为子树个数)。
  5. 所有叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

应该说以上定义还是清晰易懂的。然而前一段时间我因为学习B-tree而查阅”Introduction to Algorithms”(以下简称”ITA”)一书时,却发现关于B-tree定义的一些有趣的区别。这里我摘录该书中关于B-tree定义的原文如下:

A B-tree T is a rooted tree (whose root is T.root) having the following properties:

  1. Every node x has the following attributes:
    1. x.n, the number of keys currently stored in node x,
    2. the x.n keys themselves, x.key1, x.key2, …, x.keyx.n, stored in nondecreasing order, so that x.key1 ≤ x.key2 ≤ … ≤ x.keyx.n,
    3. x.leaf, a boolean value that is TRUE if x is a leaf and FALSE if x is an internal node.
  2. Each internal node x also contains x.n+1 pointers x.c1, x.c2, …, x.cx.n+1 to its children. Leaf nodes have no children, and so their ci attributes are undefined.
  3. The keys x.keyi separate the ranges of keys stored in each subtree: if ki is any key stored in the subtree with root x.ci, then k1 ≤ x.key1 ≤ k2 ≤ x.key2 ≤ … ≤ x.keyx.n ≤ kx.n+1.
  4. All leaves have the same depth, which is the tree’s height h.
  5. Nodes have lower and upper bounds on the number of keys they can contain. We express these bounds in terms of a fixed integer t ≥ 2 called the minimum degreeof the B-tree:
    1. Every node other than the root must have at least t-1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.
    2. Every node may contain at most 2t-1 keys. Therefore, an internal node may have at most 2t children. We say that a node is full if it contains exactly 2t-1 keys.

你是不是已经发现了某些差异?我们暂且不做分析,而是来看看更多权威资料是如何定义B-tree的。

先看经典巨著,高德纳的”The Art of Computer Programming”(以下简称”TAOCP”)关于B-tree的定义,摘录如下:

A B-tree of order m is a tree that satisfies the following properties:

  1. Every node has at most m children.
  2. Every node ,except for the root and the leaves, has at least m/2 children.
  3. The root has at least 2 children (unless it is a leaf).
  4. All leaves appear on the same level, and carry no information.
  5. A nonleaf node with k children contains k-1 keys.

(As usual, a “leaf” is a terminal node, one with no children. Since the leaves carry no information, we may regard them as external nodes that aren’t really in the tree, so that Λ is a pointer to a leaf.)

这里要补充说明,高德纳的B-tree定义中第二条中的m/2实际上是要向上取整的,亦即⌈m/2⌉,这点在原著下文中也有说明。

自然,B-tree创始人的文档我们不能不看,同样摘录R. Bayer, E. McCreight的”Organization and Maintenance of Large Ordered Indexes“(以下简称”OMLOI”)中关于B-tree的定义如下:

Def. 2.1. Let h ≥ 0 be an integer, k a natural number. A directed tree T is in the class τ(k, h) of B-tree if T is either empty (h=0) or has the following properties:

  1. Each path from the root to any leaf has the same length h, also called the height of T, i.e., h=number of nodes in path.
  2. Each node except the root and the leaves has at least k+1 sons. The root is a leaf or has at least two sons.
  3. Each node has at most 2k+1 sons.

如果你感兴趣的话,不妨再去看一下Wikipedia上关于B-tree的介绍,再与以上定义做一个对比。

好了,以上罗列这么多的定义,现在是时候看一看这些定义的差别的了。细心观察后不难发现:
首先严版定义参考了TAOCP的定义,所以这两个可以归为一个;
然后,关于leaf的定义并不统一,TAOCP主张leaf是包含数据的最底层结点的下一层,而IOA与OMLOI主张最底层包含数据的结点即为leaf;
最后一点,也是之前让我疑惑的一点,即关于B-tree的Order,或翻译为“度”的定义并不统一。IOA定义了一个称为“最小度数t”的固定整数,表 示非根的内结点至少拥有的子女数量,并且规定内结点最多拥有的子女数为2t。TAOCP定义的度m是一个结点所能拥有的最大子女数,并且非根内结点至少拥 有⌈m/2⌉个子女,这样,非根内结点的最小子女数量并不固定,而是和度m的奇偶性有关。而OMLOI并没有明确给出度的概念,而是给出了一个自然数k, 表示非根内结点至少拥有的关键字(key)的数量,并且最多能拥有的key数量为2k,亦即最大子女数是2k+1。

关于leaf定义的二义性不难理解,因为B-tree本身的实现就有很多种,有些实现中,叶子结点本身可能包含了关键字与数据的全部信息,另外一些 设计中叶子结点也许仅仅包含了指向这些数据的指针。只要能恰当表示“B-tree的最底层”这个概念,所有这些定义都是可行的。所以说leaf如何定义并 不关系到B-tree的核心思想。

我们探究的重点应该是B-tree“度”这个概念的不同定义。我一直试图统一不同著作中关于度的概念,比如我希望将IOA中的t经过一些数学上的转 化而得到TAOCP中的m,但这样的尝试得到的结果更加奇怪,因为按照IOA的定义,最简的B-tree是一棵2-3-4 tree,亦即每个非根内结点可以有2个,3个,4个子女,而按照TAOCP,最简的B-tree是一棵2-3 tree,亦即每个非根内结点可以拥有2个,3个子女。

这是怎么回事,难道大师们的定义有矛盾?经过一段时间的思考和积累,我渐渐的有了自己的结论。理解上述“矛盾”的基本要点是理解设计B-tree的目的(初衷)与核心思想。还记得正餐开始时 我们提及的几个要点吗?是的,B-tree的设计目的是为了减少磁盘I/O的次数,一切的定义与设计思想都要为这个目的服务; B-tree的核心思想是,这个数据结构是一棵平衡的多路查找树,所有的叶子结点都在同一层次,拥有相同的深度。为了维护这个性质,B-tree在插入与 删除操作时需要在适当的时机分裂与合并结点; 而为了配合B-tree特定的插入与删除操作能顺利进行,B-tree要求内结点满足至少“半满”,至多“全满”的性质,这样
1. 在一个新key插入一个原本全满的结点而需要分裂时,我们总能找到合理的分割点且满足结点分裂后产生的新结点刚好满足半满,
2. 删除操作则能保证让经过删除后不满足半满性质的结点经过合并而满足至少半满,
3. 与此同时还能维护整棵树平衡的性质。
“度”的概念就是为了定量描述这两个性质而引进的度量(当然,半满与全满并不是维护B-tree平衡的必要条件,比如B*-tree要求非根内结点至少2/3满,至多全满,同时这也就意味着相较于B-tree其插入与删除操作必然略有差别)。

有了以上概念,我们可以试图解释关于“度”的定义的“矛盾”了。实际上我在引用各著作的关于B-tree的定义时并没有按照时间顺序,历史上是先有 OMLOI再有TAOCP再有IOA。先来看OMLOI,按照Wikipedia上的说法,同样也存在其他B-tree的定义规定最少的非根内结点key 数量为k,而这些定义对最大key数量的规定并不统一,亦即最大key数量不确定,可能为2k,也可能为2k+1。高德纳在TAOCP中通过定义非根内结 点的最大子女数m来避免了这个问题。但是根据TAOCP的原始定义(高德纳在后文中对原始定义做了优化),这样的B-tree(或者说经典的B- tree)在进行插入删除操作时,如果遇到一个结点需要分裂或者两个结点需要合并,那么在DFS过程中需要回溯到父结点,这意味着一次多余的磁盘I/O。那么有没有办法去掉这一多余的磁盘I/O呢?Wikipedia中有简单提到:

An improved algorithm supports a single pass down the tree from the root to the node where the insertion will take place, splitting any full nodes encountered on the way. This prevents the need to recall the parent nodes into memory, which may be expensive if the nodes are on secondary storage. However, to use this improved algorithm, we must be able to send one element to the parent and split the remaining U−2 elements into two legal nodes, without adding a new element. This requires U = 2L rather than U = 2L−1, which accounts for why some textbooks impose this requirement in defining B-trees.

大意即为,可以找到一种改进算法,让插入操作的一趟DFS过程中遇到全满结点就进行分裂操作,而不是等到加入一个新key发生溢出时才进行分裂操 作,这样就不需要重新读取父结点到主存。然而这样的改进要求全满与半满的数量关系严格满足倍数关系,亦即U=2L(这里U即Knuth的m),因为我们需 要保证分裂全满结点时在提取一个key并将其上升到父结点后,剩下的结点仍然能正常分裂为两个合法的新结点。

我们可以看到IOA中关于B-tree的定义正是为了满足这些要求而引入的。IOA定义的t是半满情况下一个非根内结点的子女数,亦即此时该结点有 t-1个key。我们可以发现,全满结点拥有2t个子女,亦即2t-1个key,若需要分裂,那么在提取一个key后剩下2t-2个key,正好可以分为 两个拥有t-1个key的半满结点。这样,我们可以认为IOA实际上是对经典的B-tree做了一个小小的改进,由此也必然的导致了定义上的细微差别了。

总的来说,B-tree的多种定义只是形式上的约束,最终目的都是为了描述这个平衡的多路查找树的核心性质。以上的分析仅仅是我自己的思考,希望能够对大家更好的理解B-tree有所帮助。

餐后甜点

从决定写作此文而动键盘到写完全文,已经过去几乎一周。我一直基于自己的理解在写这篇文章,担心出现偏差,曾试图Google相关的参考文章,以失败告终; 为了保险起见在知乎上求助,呼应者也寥寥。我特地问了@淘宝丁奇, 他也觉得这个问题只是形式的不同。我回想了一下当初研究这个问题的动机,可能大部分人都没有在意过这个问题?但也许是我的完美主义,我无法容忍不同参考书 关于B-tree的不同定义问题,这个问题就像一粒沙子在我眼里,总希望能理顺这之间的关系,或者找出一个统一的方法,因此有了本文。鄙人才疏学浅,能力 有限,如果有任何Bug与疑问,欢迎大家不吝赐教,留言或电邮都可:)

References

  • B-tree on Wikipedia.
  • 《数据结构(C语言版)》; 严蔚敏,吴伟民; 清华大学出版社,2007.
  • Introduction of Algorithms, 3rd Edition; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein; The MIT Press, 2009.
  • The Art of Computer Programming, 2nd Edition; Donald E. Knuth; Addison-Wesley, 1998.
  • Organization and Maintenance of Large Ordered Indexes; R. Bayer, E. McCreight; Acta Informatica, Vol. 1, Fasc. 3, 1972.

Posted 2012/03/18 by linou518 in Oracle Base

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: