共计 2564 个字符，预计需要花费 7 分钟才能阅读完成。
自动写代码机器人，免费开通
这篇文章主要介绍了 mysql 的索引底层之实现原理是什么，具有一定借鉴价值，需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获。下面让丸趣 TV 小编带着大家一起了解一下。
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 特性：
1、关键字集合分布在整颗树中；
2、任何一个关键字出现且只出现在一个节点中；
3、每个节点存储 date 和 key；
4、搜索有可能在非叶子节点结束；
5、一个节点中的 key 从左到右非递减排列；
6、所有叶节点具有相同的深度，等于树高 h。
B-Tree 上查找算法的伪代码如下：
三、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 更适合外存索引。
五、MySQL 索引实现
1、MyISAM 引擎使用 B +Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址；
MyISAM 主索引和辅助索引在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复；
2、InnoDB 的数据文件本身就是索引文件，叶节点包含了完整的数据记录，这种索引叫做聚集索引。
因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（MyISAM 可以没有），如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键。
InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址；
辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录；
3、页分裂问题
如果主键是单调递增的，每条新记录会顺序插入到页，当页被插满后，继续插入到新的页；
如果写入是乱序的，InnoDB 不得不频繁地做页分裂操作，以便为新的行分配空间。页分裂会导致移动大量数据，一次插入最少需要修改三个页而不是一个页。
如果频繁的页分裂，页会变得稀疏并被不规则地填充，所以最终数据会有碎片。
六、总结
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助
1、为什么不建议使用过长的字段作为主键？
2、为什么选择自增字段作为主键？
3、为什么常更新是字段不建议建立索引？
4、为什么选择区分度高的列作为索引？区分度的公式是 count(distinct col)/count(*)
5、尽可能的使用覆盖索引
七、优化 LIMIT 分页查询
SELECT * FROM table where condition LIMIT offset , rows ;上述 SQL 语句的实现机制是：
1、从“table”表中读取 offset+rows 行记录。
2、抛弃前面的 offset 行记录，返回后面的 rows 行记录作为最终的结果。
覆盖索引：
select a.id, sid, parent_s_id from cashpool_account_relationship a join (select id from cashpool_account_relationship LIMIT 1000000,10)b on a.id = b.id;
select id, sid, parent_s_id from cashpool_account_relationship where id =(select id from cashpool_account_relationship LIMIT 1000000,1) LIMIT 10;
八、Q A
1、InnoDB 支持 hash 索引吗？– 马欣
InnoDB 是支持 hash 索引的，不过其支持的 hash 索引是自适应的，InnoDB 存储引擎会根据表的使用情况自动为表生成 hash 索引，不能人为干预是否在一张表中生成 hash 索引。
2、InnoDB 主键索引的叶节点含完整的数据记录，那主键索引文件要比数据文件大吗？– 徐财厚
1）. 在 Innodb 引擎中，主键索引中的叶子结点包含记录数据，主键索引文件即为数据文件。
2）. 在 tables 表中统计的 data_length 数据为主键索引大小，index_length 为统计的这个表中所有辅助索引（二级索引）索引的大小。
感谢你能够认真阅读完这篇文章，希望丸趣 TV 小编分享 mysql 的索引底层之实现原理是什么内容对大家有帮助，同时也希望大家多多支持丸趣 TV，关注丸趣 TV 行业资讯频道，遇到问题就找丸趣 TV，详细的解决方法等着你来学习!
向 AI 问一下细节丸趣 TV 网 – 提供最优质的资源集合！
