什么是索引？什么是索引？索引原理

什么是索引（什么是索引？索引原理） 索引是一种存储结构，它对数据库表中的一个或多个列的值进行分隔和物理排序，使程序能够快速找到所需的内容。

索引是一种数据结构（平衡树不是二叉树），即B-tree，B+树，通过不断缩小要获取的数据范围来过滤掉最终想要的结果，同时将随机事件转化为顺序事件。

B-树：

1.定义任何非叶子节点最多有M个孩子；和 M>2;

2.根节点的子节点数为[2,M]；

3.根节点以外的非叶子节点的子节点个数为[M/2,M]；

4.每个节点存储至少M/2-1个（向上取整），最多M-1个关键字； （至少 2 个关键字）

5.非叶子节点的关键字个数=儿子的指针个数-1；

6.非叶子节点的关键字：K[1], K[2], &;, K[M-1];和 K[i] < K[i+1];

7.指向非叶子节点的指针：P[1], P[2], ..., P[M];其中 P[1] 指向小于 K[1] 的关键字

子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字所属的子树(K[i-1],K[i] );

8.所有叶子节点都在同一层；

B树的搜索，从根节点开始，对节点中的（有序的）关键字序列进行二分查找，如果

如果命中则结束，否则进入查询关键字所属范围的子节点；重复直到对应的子指针为

空的，或者已经是叶子节点；

B-tree 的特征：

1.关键字集分布在整个树中；

2.任何关键字只出现在一个节点；

3.搜索可能在非叶子节点处结束；

4.搜索性能相当于在完整的关键字集合中进行二分查找；

5.自动层次控制；

由于根节点以外的非叶子节点都受到限制，所以它至少包含M/2个子节点，保证该节点至少有

利用率，其底部搜索性能为：

其中，M为非叶子节点子树的最大个数，N为关键字总数；

所以B-tree的性能总是等价于二分查找（不考虑M值），不存在B-tree平衡的问题；

由于M/2的限制，插入节点时，如果节点已满，需要将节点拆分成两部分，各占

M/2 节点；删除节点时，需要合并两个小于M/2的兄弟节点；

B+树是B-tree的一种变体，也是一种多路搜索树：

1.其定义与B-tree基本相同，除了：

2.非叶子节点的子树指针个数与关键字个数相同；

3.非叶子节点的子树指针P[i]指向键值属于[K[i],K[i+1]的子树]

(B-tree是开区间);

5.给所有叶子节点添加一个链指针；

6.所有关键字都出现在叶子节点中；

B+的特点：

1.所有关键字出现在叶子节点的链表（密集索引）中，链表中的关键字正好

是有序的；

2.不可能命中非叶子节点；

3.非叶子节点相当于叶子节点的索引（稀疏索引），叶子节点相当于存储

（关键字）数据的数据层；

4.更适合文件索引系统；

郑重声明：本文版权归原作者所有，转载文章仅出于传播更多信息之目的。如果作者信息标注有误，请尽快联系我们修改或删除，谢谢。