◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。
什么是索引(什么是索引?索引原理)索引是单独的,物理的对数据库表中一列或多列的值进行排序的一种存储结构,让程序能够快速找到所需内容。
索引是一种数据结构(平衡树非二叉),即B树,B+树,通过不断的缩小想要获得数据的范围来筛选出最终想要的结果,同时把随机的事件变成顺序的事件。
B树:
1.定义任意非叶子结点最多只有M个儿子;且M>2;
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])的子树;
B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果
命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为
2.任何一个关键字出现且只出现在一个结点中;
4.其搜索性能等价于在关键字全集内做一次二分查找;
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少
其中,M为设定的非叶子结点最多子树个数,N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占
M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;
3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树
1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好
3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储
◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。