B-树

1.B-树的概念

是一种多路搜索树，适合在磁盘等直接存取设备上组织动态的查找表，可能部分数据不在内存中。它作为索引文件的一种重要存储结构（数据库索引）

对于m阶（m>=3）B-tree,满足如下特性：

1）树中每个节点至多有m个节点

2）根节点子树个数在：2---m（根非叶子节点）

3）非根节点子树个数在：m/2(向上取整)---m。

4）排列规则：所有叶节点在同一层，按照递增次序排列。

由于节点关键字个数比子树个数少1，故而关键字个数满足：

 

1）根节点关键字个数在：1---m-1（根非叶子节点）

2）非根节点 关键字 个数在：m/2(向上取整)-1---m-1。

 

 

2.B-tree的搜索特性

 

1）关键字集合分布在整颗树中；

2）.任何一个关键字出现且只出现在一个结点中；

3）.搜索有可能在非叶子结点结束；

4）.其搜索性能等价于在关键字全集内做一次二分查找；

5）.自动层次控制；

 

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少

利用率，其最底搜索性能为：O(logn)

n个关键字的m阶B-tree的最大深度<=1+log_(n+1)/2(其中_代表是底为m/2的下界)

 

 

 

3.B-树的诞生

a.就树本身来说

  由于在之前我们已经知道了，简单二叉树，排序二叉树，然后到平衡二叉树，对树的结构一步步的进行了改进！那么它为什么要改进？目的就是为了找到最优的数据存储方式，通过这样存储数据，使得查找，插入等基本的数据操作变得非常快捷，方便，节约时间和空间！在每次改进都有很大的进步。但是对于这些二叉树，最大的局限是在内存操作级别效率是很高的，但是也会随着高度的增加，效率逐渐降低！时间也许就会花在遍历查找！尤其是数据量非常之大，如百万级的数据，你想想要是建立一个二叉树，其高度至少是log（M+1），M为数据量，如果M=100000000（1亿），那么高度是多少可想而知！况且这么多数据有时候也不可能全部存入内存！！那么怎么办？就是要寻找一种数据结构，以最低的高度存储最多的数据量！效率要足够高，这样，多路搜索树应运而生！

 

b.就硬件层次来说

  其来源起源于提高外部数据的读取速度，因为有时候读取的数据非常之多，不可能全部读入内存，而是部分存于外部存储器，这样进行数据查找等就相当费时

那么，怎么办？就要找一种有效的数据组织方式，使在外存查找数据的时间减到最少！

具体详细说明见：http://blog.csdn.net/v_july_v/article/details/6530142

上面博文中，数据全部都是在外存，是需要什么数据才将其读入内存，故而这就要求，数据组织方式要求树尽量低，这样进行的I/O操作就会降低到最少！如下：

 

为了简单，这里用少量数据构造一棵3叉树的形式，实际应用中的B树结点中关键字很多的。上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件内容在硬盘中的存储位置；p1表示指向17左子树的指针。

假如每个盘块可以正好存放一个B树的结点（正好存放2个文件名）。那么一个BTNODE结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址。

 

下面，咱们来模拟下查找文件29的过程：

a.根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作 1次】    

b.此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。

c.根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作 2次】    

d.此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发,26<29<30，因此我们找到指针p2。

e.根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作 3次】    

f.此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。

分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。

 

当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘4次，最多5次，而且文件越多，B树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。

 

 

4.B-tree的基本操作

这里有一个关于插入和删除操作的模拟操作动画，可以看到插入删除的过程（非常好哦）：http://slady.net/java/bt/view.php

a.插入

 2.删除

插入与删除的转换-----------------

 

5.  5序B树，那咱们试着删除C

 于是将删除元素C的右子结点中的D元素上移到C的位置，但是出现上移元素后，只有一个元素的结点的情况。

又因为含有E的结点，其相邻兄弟结点才刚脱贫（最少元素个数为2），不可能向父节点借元素，所以只能进行合并操作，于是这里将含有A,B的左兄弟结点和含有E的结点进行合并成一个结点。

 

 

 

这样又出现只含有一个元素F结点的情况，这时，其相邻的兄弟结点是丰满的（元素个数为3>最小元素个数2），这样就可以想父结点借元素了，把父结点中的J下移到该结点中，相应的如果结点中J后有元素则前移，然后相邻兄弟结点中的第一个元素（或者最后一个元素）上移到父节点中，后面的元素（或者前面的元素）前移（或者后移）；注意含有K，L的结点以前依附在M的左边，现在变为依附在J的右边。这样每个结点都满足B树结构性质。

从以上操作可看出：除根结点之外的结点（包括叶子结点）的关键字的个数n满足：（ceil(m / 2)-1）<= n <= m-1，即2<=n<=4。这也佐证了咱们之前的观点。删除操作完。

 

 

5.为什么设置树的限制策略？它具体的用途？

第一问，是为了提高空间的利用率，在B-树中要求最低是m/2(非根)，而在B*中是要求2/3m,进一步提高了利用率，使树进一步“紧凑”。

第二问，具体用途就是在文件系统，在磁盘等直接存取设备上组织动态的查找表。

 

6.扩展

a.B+树：B-树的变种，也是一种多路搜索树。

  特点（与B-树的差异）：

  1）有n棵子树的节点中包含有n个关键字。

  2）所有的叶子节点中包含了全部关键字信息，及指向含这些关键字记录的指针，且叶子节点本身依照关键字大小自小而大顺序链接。

  3）所有的非终端节点可以看成是索引部分，节点中仅含有其子树（根节点）中的最大（或最小）的关键字。

b.B-与B+树哪个优？

引用http://blog.csdn.net/v_july_v/article/details/6530142

 

B树：有序数组+平衡多叉树；

B+树：有序数组链表+平衡多叉树；

B*树：一棵丰满的B+树。

    在大规模数据存储的文件系统中，B~tree系列数据结构，起着很重要的作用，对于存储不同的数据，节点相关的信息也是有所不同，这里根据自己的理解，画的一个查找以职工号为关键字，职工号为38的记录的简单示意图。(这里假设每个物理块容纳3个索引，磁盘的I/O操作的基本单位是块（block),磁盘访问很费时，采用B+树有效的减少了访问磁盘的次数。）

对于像MySQL，DB2，Oracle等数据库中（数据库中数据实际存于磁盘）的索引结构得有较深入的了解才行，建议去找一些B 树相关的开源代码研究。

 

 

走进搜索引擎的作者梁斌老师针对B树、B+树给出了他的意见（为了真实性，特引用其原话，未作任何改动）： “B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

    比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。

    B树比如你的例子中查，17的话，一把就得到结果了，

    有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。

    另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。（利用了内存的缓存机制，预存？）”非常感谢。

    Bucket Li："mysql 底层存储是用B+树实现的，知道为什么么?(上面红色粗体)。内存中B+树是没有优势的，但是一到磁盘，B+树的威力就出来了（主要是range-query功能）"。

 

我从上面也总结：

1).B+树好处在于要连续访问节点，如从1--10，是连续的，这取决于B+的存储结构，因为B+树的叶子结点都用链接指针连起来了，故而连续访问非常快

    而这是B树的弱点，它没有B+这样的存储特点，故而更适合单个查询，不论成不成功，都很快。故而是B+树用于数据库主要原因，数据库数据大多数在磁盘中（B与B+差不多），也经常涉及连续访问（B+）！

2).基于频率的搜索，属于单个查询，B树合适

 

 

c.为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？

1) B+-tree的磁盘读写代价更低

    B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

    举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2) B+-tree的查询效率更加稳定

    由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

评论

2 楼 QAZ503602501 2013-11-21  

牛死人了！！！

1 楼 337240552 2012-10-16  

好东西