【深入理解MySQL的索引数据结构】

🔊博主介绍

🌾阅读前，快速浏览目录和章节概览可帮助了解文章结构、内容和作者的重点。了解自己希望从中获得什么样的知识或经验是非常重要的。建议在阅读时做笔记、思考问题、自我提问，以加深理解和吸收知识。💡在这个美好的时刻，本人不再啰嗦废话，现在毫不拖延地进入文章所要讨论的主题。接下来，我将为大家呈现正文内容。

🥤本文内容

📕索引底层数据结构与算法

📙索引数据结构

📘二叉树

📘红黑树

📘Hash

• 对索引的key进行一次hash计算就可以定位出数据存储的位置，很多时候Hash索引要比B+Tree索引更高效
• 仅能满足 “=”，“IN”，不支持范围查询，hash冲突问题。

📘B-Tree

• 索引元素不重复
• 从左到右递增排列。

📘B+Tree

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能
• 可以支持范围查询，有双向指针，假如查询Col1>30通过双向指针直接可以查询出来大于30的数据，而不是像B-Tree一样需要重新从根节点查询。

📙表在不同存储引擎的存储结构

📘MyISAM存储引擎索引实现

📚文件结构

• .frm结尾的文件：表结构文件
• .MYD结尾的文件：数据文件
• .MYI结尾的文件：索引文件

📚非聚集索引

假设查询Col1=30，这个时候会先去.MYI结尾的索引文件找到磁盘地址0XF3，然后再去.MYD结尾的数据文件获取这一行数据。索引和数据分开存储就叫做非聚集索引。

📘InnoDB存储引擎索引实现

📚文件结构

• .frm结尾的文件：表结构文件
• .ibd结尾的文件：数据和索引文件，按照B+Tree组织的一个索引结构文件

📚聚集索引

叶节点包含整行记录，例如Col1=30会把其他行（Col2、Col3）的数据放到一起，这就是聚集索引。从结构上来说，聚集索引直接就获取到了整行数据性能比非聚集索引效率更高。

📙为什么DBA总推荐使用整型自增主键做索引

前面提到 InnoDB存储引擎中.ibd文件必须要用B+Tree来组织索引结构。

• 如果表里面有主键，那么就可以直接使用主键作为B+Tree来组织索引结构。
• 如果表里面没有创建主键，它会从表中选择一列所以数据不重复的列作为主键。
• 如果没有选到不重复的列，这个时候MySQL才会自增隐藏列作为主键。
• 通常情况都会自己选择一列作为主键，而不是交由MySQL自增隐藏列，减少MySQL的工作。

选择整型效率更快。

• 如果以字符串作为主键，那么要逐个字符对比ASCII码，这种工作模式在对比过程中，如果二个对比结果前面相同，就最后一个字符不相同，浪费的性能还是很高的。
• 整型存储的空间更小，会节约硬件资源。

假设我先插入8后插入7，即非自增插入数据，这个B+Tree结果是如何变化的呢？
5/6/8这个大节点放满了，插入7
放不下了，进行拆分平衡

假设后面插入9/10这种自增的数据，B+Tree会直接往后面开一个节点，性能比对来说，肯定是自增的会高一些。

📙为什么非主键索引结构叶子节点存储的是主键值？

非主键索引结构叶子节点存储主键值的原因主要有两个：

• 保持一致性：当数据库表进行DML（数据操纵语言，如INSERT、UPDATE、DELETE）操作时，同一行记录的页地址可能会发生改变。由于非主键索引保存的是主键的值，而非实际的数据记录，因此当数据记录发生移动或变更时，非主键索引无需进行更改，只需保持与主键值的对应关系即可，从而保持索引的一致性。
• 节省存储空间：在InnoDB存储引擎中，数据本身已经按照主键索引的B+树结构进行存储。如果非主键索引也存储整行数据，那么每个非主键索引都会存储一份数据，这将导致大量的数据冗余和存储空间的浪费。而只存储主键值的方式可以极大地节省存储空间，因为主键索引已经包含了完整的数据记录。

非主键索引通过存储主键值，可以在查询时通过主键值快速定位到数据记录所在的位置，从而提高查询效率。

先用二级索引找到主键索引，然后使用主键索引回表去查询对应的数据。

📙MySQL最左前缀优化原则是怎么回事

• 先对比name大小，比较字符大小，HanMeimei<Jeff
• 然后对比age大小，比较年龄大小，30<31<32
• 最后对比position大小，dev<manager

EXPLAIN SELECT * FROM employees WHERE name = 'Bill' and age = 31;
EXPLAIN SELECT * FROM employees WHERE age = 30 AND position = 'dev';
EXPLAIN SELECT * FROM employees WHERE position = 'manager';|

根据上述的联合索引，分析上述SQL，只有第一条SQL会走索引。

• 联合索引遵循最左前缀原则，先使用name进行查找，这是name已经排好序了，直接可以查询。
• 然后使用age去查找，发现30,31,32,28,22,30,30，这个是没有排序的，就走全表扫描了。
• 后面就不会使用position继续查找了。

🔔以上就是今天要讲的内容，阅读结束后，反思和总结所学内容，并尝试应用到现实中，有助于深化理解和应用知识。与朋友或同事分享所读内容，讨论细节并获得反馈，也有助于加深对知识的理解和吸收。

🔔如果您需要转载或者搬运这篇文章的话，非常欢迎您私信我哦~

📥博主的话

🚀🎉希望各位读者大大多多支持用心写文章的博主，现在时代变了，🚀🎉 信息爆炸，酒香也怕巷子深🔥，博主真的需要大家的帮助才能在这片海洋中继续发光发热🎨，所以，🏃💨赶紧动动你的小手，点波关注❤️，点波赞👍，点波收藏⭐，甚至点波评论✍️，都是对博主最好的支持和鼓励！

• 💂 博客主页： Java程序员廖志伟
• 🌥 哔哩哔哩：Java程序员廖志伟
• 🎏个人社区：幕后大佬
• 👉开源项目：java_wxid
• 🔖个人微信号： SeniorRD

🎥经过多年在CSDN创作上千篇文章的经验积累，我已经拥有了不错的写作技巧，与清华大学出版社签下了四本书籍的合约，并将陆续在明年出版。这些书籍包括了基础篇、进阶篇、架构篇的📌《Java项目实战—深入理解大型互联网企业通用技术》📌，以及📚《解密程序员的思维密码–沟通、演讲、思考的实践》📚。具体出版计划会根据实际情况进行调整，希望各位读者朋友能够多多支持！

京东商城购买链接：https://item.jd.com/10103130513615.html

京东商城购买链接：https://item.jd.com/14152451.html

京东商城购买链接：https://item.jd.com/14152451.html

京东商城购买链接：https://item.jd.com/14152451.html