数据库索引技术中经常使用的B树和B+树详解

B树

B树，又叫做B-Tree。他是一种平衡的多路查找树。主要面向动态查找，通常用在文件系统中。

1、B树的定义：

一颗m阶的B树或者为空树，满足以下的几个条件：

（1）所有的叶子节点都在同一层上面，并且叶子节点上面不存储信息。叶子节点的双亲节点为终端节点。

（2）树中的每个节点至多有m颗子树。

（3）若根节点不是终端节点，则根节点至少有两颗子树。

（4）除了根节点以外的所有非终端节点至少有m/2颗子树。

（5）所有的非终端节点都包含三个信息：关键码个数、关键码和指向子树根节点的指针。其中关键码是按照从小到大进行排列的。

  B树的叶子节点通常可以看做是查找失败的节点，称为外节点。实际上这些外节点是不存在的，指向这些节点的指针为空，所以B树的叶子节点可以不用画出来。由于叶子节点都在出现在同一层上面，所以B树是高度平衡的。如下图，是一颗4阶的B树。

                  

2、B树的查找（数据库中索引查找的体现）

  B树的查找类似于二叉排序树的查找，不同的是B树的每个节点是含有多关键码的有序列表，在到达某个节点时，先在有序表中查找，若找到，则查找成功；否则，按照指针到相应的子树中查找，到达叶子节点时，查找失败。

  在B树上的查找过程是一个顺时针查找节点和在节点中查找关键码交叉进行的过程。由于B树通常存储在磁盘上，则前一个查找操作是在磁盘上进行，而后一个查找操作是在内存中进行，即在磁盘上找到某个节点后，先将节点的信息读入内存，然后查找等于k的关键码。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费的时间多得多，因此，在磁盘上进行查找的次数，即待查找关键码所在节点在B树的层数，是决定B树查找效率的首要因素。

B+树

B+树，是B树的一个变种。一颗m阶的B+树在结构上与m阶B树相同，但在关键码的内部安排上与B树有所不同。

1、B+树定义

一颗m阶的B+树满足以下条件：

（1）树中的每个节点至多含有m颗子树。

（2）具有m颗子树的节点含有m个关键码，即每一个关键码对应一颗子树。

（3）关键码K(i)是他所对应子树的根节点的最大（或最小）的关键码。

（4）所有的终端节点包含了全部关键码信息，以及执行对应记录的指针。

（5）各终端节点按关键码的大小顺序次链在一起，形成单链表，并设置头指针。

  与B树不同的是，B+树只在终端节点存储记录，内部节点存储关键码，但是这些关键码只是用于引导查找的，这意味着内部节点在结构上与终端节点有显著区别。内部节点存储关键码用于引导查找，把每个关键码与一个指向子女节点的指针相关联；终端节点存储记录，在B+树纯粹作为索引的情况下则存储关键码和指向对应记录的指针。

  如下图，是一个3阶的B+树，通常在B+树上有两个头指针，一个指向根节点，一个指向关键码的最小的终端节点。因此，可以对B+树进行两种查找操作：一种是从最小关键码开始进行顺序查找，另一种是从根节点开始查找。

                           

  由于B+树的内部节点只是用来引导索引的，并不提供实际记录的访问，所以在B+树从根节点出发进行查找，即使在一个内部节点找到了待查关键码，也必须到达包含有该关键码的终端节点。所以，B+树特别适合范围查找，一旦找到了范围中的第一个记录，通过顺序处理节点中的其余记录，就可以找到范围中的全部记录。