平衡多路搜索树
2.3.3 平衡多路搜索树
为了提高页的利用率，我们希望树的一个节点存储的信息较多；为了减少一次检索的IO操作次数，我们希望搜索树的高度很小。基于这两个目的，平衡多路搜索树被提出。下面介绍两种最常用的平衡多路搜索树：B-树和B+树。
2.3.3.1 B-树
一棵阶数为mm的B-树定义如下：
- 如果根结点不是叶结点，则其至少有两棵子树。
- 每一个非根的分支结点都有k-1个关键字和k个子树，其中 ⌈m/2⌉⩽k⩽m。
- 所有叶子结点都位于同一层次。
- 所有分支结点包含下列信息数据
,其中:
为关键字，且
为指向子树根结点的指针，且指针
所指子树中所有结点的关键字均小于
所指子树中所有结点的关键字均大于
为关键字的个数。
一棵阶数为3的B-树如下所示。
B-树的代码定义如下：
typedef struct node{ //B-树和B-树结点类型
int keynum; //结点关键字个数
KeyType key[MAXM]; //关键字数组，key[0]不使用
struct node *parent; //双亲结点指针
struct node *ptr[MAXM]; //孩子结点指针数组
}BTNode,*BTree; 在B-树中查找指定的关键字K的大致代码如下：
typedef struct{ //B树查找结果类型
BTNode *pt; //指向找到的结点
int i; //在结点中的关键字位置;
int tag; B+树是对B-树的一种变形树，它与B-树的差异在于： 一棵B+树如下所示： 前面提到二叉树之所以不适合作为索引是因为它的高度很大，导致一次检索的磁盘I/O次数很多。我们从这个角度来谈论为什么平衡多路搜索树为什么适合作为索引。 我们假设为1000，则高度为3的B+数有个关键字，则可以链接到1亿个数据记录，并且一次检索的I/O次数为3。
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
数据库索引-笔面试必考点15讲 文章被收录于专栏
Java开发之数据库索引篇，适合所有求职开发岗的同学~ 本专刊购买后即可解锁所有章节，故不可以退换哦~
