学步园

相信，从上图你能轻易的看到，一个内结点x若含有n[x]个关键字，那么x将含有n[x]+1个子女。如含有2个关键字D H
的内结点有3个子女，而含有3个关键字Q T X
有4个子女。

B
树又叫平衡多路查找树。一棵
m
阶的
B
树
(m
叉树
)
的特性如下：

1. 树中每个结点最多含有m个孩子（m>=2）；
   
   
   
   
2. 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数
   ）；
   
3. 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
   
4. 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
   
5. 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
          a)   Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
          b)   Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 
          c)   关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。
   

    针对上面第5点，再阐述下：B树中每一个结点能包含的关键字（如之前上面的D H
和Q T X

）数有一个上界和下界。这两个界可以用一个称作B树的最小度数t（t>=2）表示。

• 每个非根的结点必须至少含有m-1个关键字。每个非根的内结点至少有m个子女。如果树是非空的，则根结点至少包含一个关键字；
  
• 每个结点可包含之多2m-1个关键字。所以一个内结点之多可有2m个子女。如果一个结点恰好有2t-1个关键字，我们就说这个结点是满的（而稍后介绍的B*树作为B树的一种常用变形，B*树中要求每个内结点至少为2/3满，而不是像这里的B树所要求的至少半满
  ）；
  
• 当关键字数m=2（m=2的意思是，m
  
  
  min
  
  =2，m可以>=2）时的B树是最简单的
  （
  有很多人会因此误认为B树就是二叉查找树，但二叉查找树就是二叉查找树，B树就是B树，B树的真正最准确的定义为：一棵含有m（m>=2）个关键字的平衡多路查找树）
  
  。每个内结点可能因此而含有2个、3个或4个子女，亦即一棵2-3-4树，然而在实际中，通常采用大得多的t值。
  

B
树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk
drives)的不同，一般块的大小在1k~4k左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查
找的数据。

 

为了简单，这里用少量数据构造一棵

3
叉树的形式，实际应用中的

B
树结点中关键字很多的。上面的图中比如根结点，其中

17
表示一个磁盘文件的文件名；小红方块表示这个

17
文件的内容在硬盘中的存储位置；

p1
表示指向

17
左子树的指针。

其结构可以简单定义为：

typedef
struct
{

   
/*

文件数*/

   
int
 
file_num;

   
/*

文件名(key)*/

   
char
* file_name[max_file_num];

   
/*

指向子节点的指针*/

    
BTNode * BTptr[max_file_num+1];

    
/*

文件在硬盘中的存储位置*/

    
FILE_HARD_ADDR offset[max_file_num];

}BTNode;

假如每个盘块可以正好存放一个

B
树的结点（正好存放

2
个文件名）。那么一个

BTNode
结点就代表一个盘块，而子树指针就是存放另外一个盘块


的地址。

下面，咱们来模拟下查找文件

29
的过程：

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

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

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

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

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

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

分析上面的过程，发现需要

3
次磁盘

IO
操作和

3
次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于

3
次磁盘

IO
操作时影响整个

B
树查找效率的决定因素。

当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘

IO
操作最少

4
次，最多

5
次。而且文件越多，

B
树比平衡二叉树所用的磁盘

IO
操作次数将越少，效率也越高

。

4.


B⁺
-tree

B⁺
-tree



：是应文件系统所需而产生的一种

B-tree


的变形树。

一棵
m
阶的
B+
树和
m
阶的
B
树的差异在于：

     
1.
有
n
棵子树的结点中含有
n
个关键字；
 (而B 树
是
n
棵子树有
n+1
个关键字
)

     
2.
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。
(而B 树
的叶子节点并没有包括全部需要查找的信息
)

     
3.
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
(而B 树
的非终节点也包含需要查找的有效信息
)

 

 

a)
    


为什么说

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


的查询效率更加稳定

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

b)
    B⁺
-tree



的应用: VSAM(
虚拟存储存取法
)
文件
(
来源论文
the ubiquitous Btree

作者：
D COMER - 1979 )

 

 

5.

B^*
-tree

B*-tree
是
B⁺
-tree

的变体，在
B⁺

树非根和非叶子结点再增加指向兄弟的指针；
B*
树定义了非叶子结点关键字个数至少为
(2/3)*M
，即块的最低使用率为
2/3
（代替
B+
树的
1/2
）。给出了一个简单实例，如下图所示：

 

B+
树的分裂：当一个结点满时，分配一个新的结点，并将原结点中
1/2
的数据复制到新结点，最后在父结点中增加新结点的指针；
B+
树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*
树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制
1/3
的数据到新结点，最后在父结点增加新结点的指针。

所以，
B*
树分配新结点的概率比
B+
树要低，空间使用率更高；

 

6.

总结

     

在大规模数据存储的文件系统中，
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
，一般已启动的时候，就会主动换入内存。”非常感谢。

 

第二节、

R

树：处理空间存储问题

相信经过上面第一节的介绍，你已经对
B
树或者
B+
树有所了解。这种树可以非常好的处理一维空间存储的问题。
B
树是一棵平衡树，它是把一维直线分为若干段线段，当我们查找满足某个要求的点的时候，只要去查找它所属的线段即可。依我看来，这种思想其实就是先找一个大的空间，再逐步缩小所要查找的空间，最终在一个自己设定的最小不可分空间内找出满足要求的解。一个典型的
B
树查找如下：

 

要查找某一满足条件的点，先去找到满足条件的线段，然后遍历所在线段上的点，即可找到答案。

B
树是一种相对来说比较复杂的数据结构，尤其是在它的删除与插入操作过程中，因为它涉及到了叶子结点的分解与合并。由于本文第一节已经详细介绍了
B
树即
B+
树，下面直接开始介绍我们的第二个主角：
R
树。

 

简介

1984
年，加州大学伯克利分校的
Guttman
发表了一篇题为
“R-trees: a dynamic index structure for spatial searching”

的论文，向世人介绍了
R
树这种处理高维空间存储问题的数据结构。本文便是基于这篇论文写作完成的，因此如果大家对
R
树非常有兴趣，我想最好还是参考一下原著吧：）。为表示对这位牛人的尊重，给个引用先：

Guttman, A.; “R-trees: a dynamic index structure for spatial searching,”
ACM,
1984
, 14

R树
在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个
R
树在现实领域中能够解决的例子吧：查找
20
英里以内所有的餐厅。如果没有
R
树你会怎么解决？一般情况下我们会把餐厅的坐标
(x,y)
分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有
100
家餐厅的话，我们就要进行
100
次位置计算操作了，如果应用到谷歌地图这种超大数据库中，我想这种方法肯定不可行吧。

R
树就很好的解决了这种高维空间搜索问题。它把
B
树的思想很好的扩展到了多维空间，采用了
B
树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，
R
树就是一棵用来存储高维数据的平衡树。

好了简介就到此为止。以下，本文将详细介绍
R
树的数据结构以及
R
树的操作。至于
R
树的扩展与
R
树的性能问题，我就仅仅在文末简单介绍一下吧，这些问题最好查阅相关论文比较合适。

 

R

树的数据结构

如上所述，
R
树是
B
树在高维空间的扩展，是一棵平衡树。每个
R
树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据
R
树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。

我们在上面说过，
R
树运用了空间分割的理念，这种理念是如何实现的呢？
R
树采用了一种称为
MBR(Minimal Bounding Rectangle)
的方法，在此我把它译作“最小边界矩形”。从叶子结点开始用矩形（
rectangle
）将空间框起来，结点越往上，框住的空间就越大，以此对空间进行分割。有点不懂？没关系，继续往下看。在这里我还想提一下，
R
树中的
R
应该代表的是
Rectangle
（此处参考
wikipedia
），而不是大多数国内教材中所说的
Region
（很多书把
R
树称为区域树，这是有误的）。我们就拿二维空间来举例吧。下图是
Guttman
论文中的一幅图。

 

我来详细解释一下这张图。先来看图（
b
）吧。首先我们假设所有数据都是二维空间下的点，图中仅仅标志了
R8
区域中的数据，也就是那个
shape of data object
。别把那一块不规则图形看成一个数据，我们把它看作是多个数据围成的一个区域。为了实现
R
树结构，我们用一个最小边界矩形恰好框住这个不规则区域，这样，我们就构造出了一个区域：
R8
。
R8
的特点很明显，就是正正好好框住所有在此区域中的数据。其他实线包围住的区域，如
R9
，
R10
，
R12
等都是同样的道理。这样一来，我们一共得到了
12
个最最基本的最小矩形。这些矩形都将被存储在子结点中。下一步操作就是进行高一层次的处理。我们发现
R8
，
R9
，
R10
三个矩形距离最为靠近，因此就可以用一个更大的矩形
R3
恰好框住这
3
个矩形。同样道理，
R15
，
R16
被
R6
恰好框住，
R11
，
R12
被
R4
恰好框住，等等。所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。我想大家都应该理解这个数据结构的特征了。用地图的例子来解释，就是所有的数据都是餐厅所对应的地点，先把相邻的餐厅划分到同一块区域，划分好所有餐厅之后，再把邻近的区域划分到更大的区域，划分完毕后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止。要查找的时候就方便了吧。

下面就可以把这些大大小小的矩形存入我们的
R
树中去了。根结点存放的是两个最大的矩形，这两个最大的矩形框住了所有的剩余的矩形，当然也就框住了所有的数据。下一层的结点存放了次大的矩形，这些矩形缩小了范围。每个叶子结点都是存放的最小的矩形，这些矩形中可能包含有
n
个数据。

在这里，读者先不要去纠结于如何划分数据到最小区域矩形，也不要纠结怎样用更大的矩形框住小矩形，这些都是下一节我们要讨论的。

讲完了基本的数据结构，我们来讲个实例，如何查询特定的数据吧。又以餐厅为例吧。假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？打开地图（也就是整个
R
树），
先选择国内还是国外（也就是根结点）。然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），再选择天河区（对应第三层结点），最后选择天
河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。怎么样，其实
R
树的查找规则跟查地图很像吧？

一棵
R
树满足如下的性质：

1.
    


除非它是根结点之外，所有叶子结点包含有
m
至
M
个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于
m
。通常，
m=M/2
。

2.
    


对于所有在叶子中存储的记录（条目），
I
是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。

3.
    


每一个飞叶子结点拥有
m
至
M
个孩子结点，除非它是根结点。

4.
    


对于在非叶子结点上的每一个条目，
i
是最小的可以在空间上完全覆盖这些条目所代表的店的矩形（同性质
2
）。

5.
    


所有叶子结点都位于同一层，因此
R
树为平衡树。

 

叶子结点的结构

先来探究一下叶子结点的结构吧。叶子结点所保存的数据形式为：
(I, tuple-identifier)
。

     

其中，
tuple-identifier
表示的是一个存放于数据库中的
tuple
，也就是一条记录，它是
n
维的。
I
是一个
n
维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的
n
维空间中的点。
I=(I₀
,I₁
,…,I_n-1
)
。

下图描述的就是在二维空间中的叶子结点所要存储的信息。

 

在这张图中，
I
所代表的就是图中的矩形，其范围是
a<=I₀
<=b
，
c<=I₁
<=d
。有两个
tuple-identifier
，在图中即表示为那两个点。这种形式完全可以推广到高维空间。大家简单想想三维空间中的样子就可以了。这样，叶子结点的结构就介绍完了。

 

非叶子结点

     

非叶子结点的结构其实与叶子结点非常类似。想象一下
B
树就知道了，
B
树的叶子结点存放的是真实存在的数据，而非叶子结点存放的是这些数据的“边界”，或者说也算是一种索引。

     

同样道理，
R
树的非叶子结点存放的数据结构为：
(I, child-pointer)
。

     

其中，
child-pointer
是指向孩子结点的指针，
I
是覆盖所有孩子结点对应矩形的矩形。这边有点拗口，但我想不是很难懂吧？给张图：

 

D,E,F,G
为孩子结点所对应的矩形。
A
为能够覆盖这些矩形的更大的矩形。这个
A
就
是这个非叶子结点所对应的矩形。这时候你应该悟到了吧？无论是叶子结点还是非叶子结点，它们都对应着一个矩形。树形结构上层的结点所对应的矩形能够完全覆
盖它的孩子结点所对应的矩形。根结点也唯一对应一个矩形，而这个矩形是可以覆盖所有我们拥有的数据信息在空间中代表的点的。

我个人感觉这张图画的不那么精确，应该是矩形
A
要恰好覆盖
D,E,F,G
，而不应该再留出这么多没用的空间了。但为尊重原图的绘制者，特不作修改。

 

R

树的操作

这一部分也许是编程者最关注的问题了。这么高效的数据结构该如何去实现呢？这便是这一节需要阐述的问题。

 

搜索

R
树的搜索操作很简单，跟
B
树上的搜索十分相似。它返回的结果是所有符合查找信息的记录条目。而输入是什么？就我个人的理解，输入不仅仅是一个范围了，它更可以看成是一个空间中的矩形。也就是说，我们输入的是一个搜索矩形。

先给出伪代码：

Function
：
Search

描述：假设
T
为一棵
R
树的根结点，查找所有搜索矩形
S
覆盖的记录条目。

S1:[
查找子树
]
如果
T
是非叶子结点，如果
T
所对应的矩形与
S
有重合，那么检查所有
T
中存储的条目，对于所有这些条目，使用
Search
操作作用在每一个条目所指向的子树的根结点上（即
T
结点的孩子结点）。

S2:[
查找叶子结点
]
如果
T
是叶子结点，如果
T
所对应的矩形与
S
有重合，那么直接检查
S
所指向的所有记录条目。返回符合条件的记录。

我们通过下图来理解这个
Search
操作。

 

 

阴影部分所对应的矩形为搜索矩形。它与根结点对应的最大的矩形（未画出）有重叠。这样将
Search
操作作用在其两个子树上。两个子树对应的矩形分别为
R1
与
R2
。搜索
R1
，发现与
R1
中的
R4
矩形有重叠，继续搜索
R4
。最终在
R4
所包含的
R11
与
R12
两个矩形中查找是否有符合条件的记录。搜索
R2
的过程同样如此。很显然，该算法进行的是一个迭代操作。

 

插入

     
R
树的插入操作也同
B
树的插入操作类似。当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。显然，叶子结点的插入操作会比搜索操作要复杂。插入操作需要一些辅助方法才能够完成。

来看一下伪代码：

Function
：
Insert

描述：将新的记录条目
E
插入给定的
R
树中。

I1
：
[
为新记录找到合适插入的叶子结点
]
开始
ChooseLeaf
方法选择叶子结点
L
以放置记录
E
。

I2
：
[
添加新记录至叶子结点
]
如果
L
有足够的空间来放置新的记录条目，则向
L
中添加
E
。如果没有足够的空间，则进行
SplitNode
方法以获得两个结点
L
与
LL
，这两个结点包含了所有原来叶子结点
L
中的条目与新条目
E
。

I3
：
[
将变换向上传递
]
开始对结点
L
进行
AdjustTree
操作，如果进行了分裂操作，那么同时需要对
LL
进行
AdjustTree
操作。

I4
：
[
对树进行增高操作
]
如果结点分裂，且该分裂向上传播导致了根结点的分裂，那么需要创建一个新的根结点，并且让它的两个孩子结点分别为原来那个根结点分裂后的两个结点。

 

Function
：
ChooseLeaf

描述：选择叶子结点以放置新条目
E
。

CL1
：
[Initialize]
设置
N
为根结点。

CL2
：
[
叶子结点的检查
]
如果
N
为叶子结点，则直接返回
N
。

CL3
：
[
选择子树
]
如果
N
不是叶子结点，则遍历
N
中的结点，找出添加
E.I
时扩张最小的结点，并把该结点定义为
F
。如果有多个这样的结点，那么选择面积最小的结点。

CL4
：
[
下降至叶子结点
]
将
N
设为
F
，从
CL2
开始重复操作。

 

Function
：
AdjustTree

描述：叶子结点的改变向上传递至根结点以改变各个矩阵。在传递变换的过程中可能会产生结点的分裂。

AT1
：
[
初始化
]
将
N
设为
L
。

AT2
：
[
检验是否完成
]
如果
N
为根结点，则停止操作。

AT3
：
[
调整父结点条目的最小边界矩形
]
设
P
为
N
的父节点，
E_N
为指向在父节点
P
中指向
N
的条目。调整
EN.I
以保证所有在
N
中的矩形都被恰好包围。

AT4
：
[
向上传递结点分裂
]
如果
N
有一个刚刚被分裂产生的结点
NN
，则创建一个指向
NN
的条目
E_NN
。如果
P
有空间来存放
E_NN
，则将
E_NN
添加到
P
中。如果没有，则对
P
进行
SplitNode
操作以得到
P
和
PP
。

AT5
：
[
升高至下一级
]
如果
N
等于
L
且发生了分裂，则把
NN
置为
PP
。从
AT2
开始重复操作。

 

同样，我们用图来更加直观的理解这个插入操作。

 

    我们来通过图分析一下插入操作。现在我们需要插入
R21
这个矩形。开始时我们进行
ChooseLeaf
操作。在根结点中有两个条目，分别为
R1
，
R2
。其实
R1
已经完全覆盖了
R21
，而若向
R2
中添加
R21
，则会使
R2.I
增大很多。显然我们选择
R1
插入。然后进行下一级的操作。相比于
R4
，向
R3
中添加
R21
会更合适，因为
R3
覆盖
R21
所需增大的面积相对较小。这样就在
B8
，
B9
，
B10
所在的叶子结点中插入
R21
。由于叶子结点没有足够空间，则要进行分裂操作。

   

操作如图：

这个插入操作其实类似于第一节中
B
树的插入操作，在这里不再赘述，想必看过上面的伪代码大家应该也清楚了。

 

参考文献以及相关网址：

1.  
Organization and Maintenance of Large Ordered Indices

2.  
the ubiquitous B tree

3.  
http://en.wikipedia.org/wiki/Btree


（给出了国外一些开源地址）

4.  
http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html


（
include C++ source code
）