R树

什么是B树？

本⽂提到的「B-树」，就是「B树」，都是B-tree的翻译，⾥⾯不是减号-，是连接符-。因为有⼈把B-tree翻成「B-树」，让⼈以为「B树」和「B-

树」是两种树，实际上两者就是同⼀种树。

Mysql数据库⾥⾯的索引是基于什么数据结构了呢？

主要是基于Hash表或者B+树。

B+树的具体实现细节？B-树和B+树有什么区别呢？联合索引在B+树中如何存储呢？

要知道这些，我们需要先了解什么是B-树。数据库索引之所以要使⽤树结构存储，是因为树的查询效率⾼，⽽且可以保持有序。为什么索引不使⽤⼆

叉查找来树来实现呢？（///⼆叉查找树查询的时间复杂读是0（logN），性能已经⾜够⾼了啊，难道B树可以⽐它更快？）其实从算法逻辑上讲，⼆叉

查找树的查找速度和⽐较次数都是最⼩的，但是为我们不得不考虑⼀个现实的问题：磁盘IO。

数据库索引是存储在磁盘上的，当数据量⽐较打的时候，索引的⼤⼩可能有⼏个G甚⾄更多。当我们利⽤索引查询的时候，能把整个索引全部加载到

内存吗？不可能，能做的只有逐⼀的加载每⼀个磁盘页对应着索引树的节点。

如果我们利⽤⼆叉查找树作为索引结构，情形是什么呢？假设树的⾼度是4，查找的值是10，流程如下：

由上可以看出，磁盘IO的次数是由索引树⾼度决定，所以为了减少磁盘IO次数，我们需要减少树的⾼度，这就是B-树的特征之⼀。

B树的定义：

两种定义：⽤阶定义的B树&⽤阶定义的B树

⽤阶定义的B树：

B树⼜叫平衡多路查找树。⼀棵m阶的B树(注：切勿简单的认为⼀棵m阶的B树是m叉树，虽然存在四叉树，⼋叉树，KD树，及vp/R树/R*

树/R+树/X树/M树/线段树/希尔伯特R树/优先R树等空间划分树，但与B树完全不等同)的特性如下：

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)

b)Pi为指向⼦树根的接点，且指针P(i-1)指向⼦树种所有结点的关键字均⼩于Ki，但都⼤于K(i-1)。

c)关键字的个数n必须满⾜：[ceil(m/2)-1]<=n<=m-1。如下图所⽰：

⽤度定义的B树：

针对上⾯的5点，再阐述下：B树中每⼀个结点能包含的关键字（如之前上⾯的DH和QTX）数有⼀个上界和下界。这个下界可以⽤⼀个

称作B树的最⼩度数（算法导论中⽂版上译作度数，最⼩度数即内节点中节点最⼩孩⼦数⽬）m（m>=2）表⽰。

每个⾮根的内结点⾄多有m个⼦⼥，每个⾮根的结点必须⾄少含有m-1个关键字，如果树是⾮空的，则根结点⾄少包含⼀个关键字；

每个结点可包含⾄多2m-1个关键字。所以⼀个内结点⾄多可有2m个⼦⼥。如果⼀个结点恰好有2m-1个关键字，我们就说这个结点是满的

（⽽稍后介绍的B*树作为B树的⼀种常⽤变形，B*树中要求每个内结点⾄少为2/3满，⽽不是像这⾥的B树所要求的⾄少半满）；

当关键字数m=2（t=2的意思是，mmin=2，m可以>=2）时的B树是最简单的（有很多⼈会因此误认为B树就是⼆叉查找树，但⼆叉查找树就

是⼆叉查找树，B树就是B树，B树是⼀棵含有m（m>=2）个关键字的平衡多路查找树），此时，每个内结点可能因此⽽含有2个、3个或4个

⼦⼥，亦即⼀棵2-3-4树，然⽽在实际中，通常采⽤⼤得多的t值。

上图是⼀颗阶数为4的B树。在实际应⽤中的B树的阶数m都⾮常⼤（通常⼤于100），所以即使存储⼤量的数据，B树的⾼度仍然⽐较⼩。每

个结点中存储了关键字（key）和关键字对应的数据（data），以及孩⼦结点的指针。我们将⼀个key和其对应的data称为⼀个记录。

B-树的查询：

演⽰如下：假设查询5

插⼊：

B-树的插⼊过程⽐较复杂，我们只举⼀个最⾦典的例⼦，插⼊4

删除：11