文章目录
一、索引的本质
二、索引的数据结构
1. Hash表
2. 二叉树
3. 红黑树
4. B-Tree
5. B+Tree(B-Tree变种)
三、存储引擎的实现
1. MyISAM存储引擎实现
2. InnoDB存储引擎实现
一、索引的本质
索引是帮助MySQL高效获取数据的排好序的一种数据结构。
二、索引的数据结构
这块只是一笔带过，想要深入了解的小伙伴——点我跳转(关于数算)。
1. Hash表
不支持范围查找很少使用
2. 二叉树
左边子节点数据小于父节点数据，右边子节点数据大于父节点数据，递增数据会导致链表
3. 红黑树
二叉平衡树，高度不可控，数量为大树越高
4. B-Tree
- 叶节点具有相同的深度，叶节点的指针为空
- 所有索引元素不重复
- 叶节点的数据索引从左至右递增排列
5. B+Tree(B-Tree变种)
- 非叶子节点不存储data，只存储索引(冗余索引)，可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点有双向指针链接(首尾子节点还通过指针连接)，提高区间访问的性能，范围查找
三、存储引擎的实现
1. MyISAM存储引擎实现
- MyISAM索引文件和数据文件是分离的(非聚集)
- frm文件：存储这张表的表结构
- MYD文件：存储这张表的所有数据行
- MYI文件：存储这张表的索引字段
2. InnoDB存储引擎实现
- frm文件：存储这张表的表结构
- ibd文件：存储这张表的所有数据行和索引字段
- 表数据ibd文件本身就是按照B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
为什么Innodb表必须包含主键，且推荐使用整型的自增主键？
- 显式设置主键的话，会作为聚集索引。没有会默认创建一列主键rowId聚集索引
- 自增主键会按照插入数据顺序排列，自动有序
为什么非主键索引结构叶子节点存储的都是主键值？
- 节省存储空间： 通过非主键索引获取到主键值，然后再去主键索引的B+树数据结构中找到对应的行数据。
- 一致性：如果非主键索引结构叶子节点也保存一份data数据，修改数据是，需要修改非主键索引和主键索引，需要数据同步，会存在一致性问题。