mysql的索引底层之实现原理是啥
发布时间：2022-02-24 07:45:34 所属栏目：MySql教程 来源：互联网
导读：这篇文章主要介绍了mysql的索引底层之实现原理是什么，具有一定借鉴价值，需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获。下面让小编带着大家一起了解一下。 MySQL索引背后的数据结构及算法原理 一、定义 索引定义：索引（Index）是帮助MySQL高效
|
这篇文章主要介绍了mysql的索引底层之实现原理是什么，具有一定借鉴价值，需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获。下面让小编带着大家一起了解一下。 MySQL索引背后的数据结构及算法原理 一、定义 索引定义：索引（Index）是帮助MySQL高效获取数据的数据结构。 本质：索引是数据结构。 二、B-Tree m阶B-Tree满足以下条件： 1、每个节点至多可以拥有m棵子树。 2、根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)。 3、非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，如5阶B树，每个节点至少有3个子树，也就是至少有3个叉)。 4、非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针。 5、从根到叶子的每一条路径都有相同的长度（叶子节点在相同的层） 三、B+Tree B+Tree与B-Tree的差异在于： 1、B+Tree非叶子节点不存储data，只存储key； 2、所有的关键字全部存储在叶子节点上； 3、每个叶子节点含有一个指向相邻叶子节点的指针，带顺序访问指针的B+树提高了区间查找能力； 4、非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字； 四、B/B+树索引的性能分析 依据：使用磁盘I/O次数评价索引结构的优劣 主存和磁盘以页为单位交换数据，将一个节点的大小设为等于一个页，因此每个节点只需一次I/O就可以完全载入。 根据B树的定义，可知检索一次最多需要访问h个节点 渐进复杂度:O(h)=O(logdN) dmax=floor(pagesize/(keysize+datasize+pointsize)) 一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3，3层可存大约一百万数据） B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存） B+Tree内节点不含data域，因此出度d更大，则h更小，I/O次数少，效率更高，故B+Tree更适合外存索引。 （编辑：拼字网 - 核心网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐