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

什么是索引（什么是索引？索引原理）索引是一种存储结构，它对数据库表中的一个或多个列的值进行分隔和物理排序，使程序能够快速找到所需的内容。
索引是一种数据结构（平衡树不是二叉树），即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.更适合文件索引系统；

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