深入理解Mysql索引底层数据结构与算法

索引是帮助MySQL高效获取数据的排好序的数据结构
数据结构网站

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引的数据结构
层层递进理解最终的B+树：二叉树->红黑树->B树->B+树

image.png
二叉树
单边增长的倾斜问题，变相为链表，查找效率低，与全表扫描差别不大
RBTree-红黑树
大数据量情况下，高度不可控
image.png

B-Tree
叶节点具有相同的深度，叶节点的指针为空
所有索引元素不重复
节点中的数据索引|从左到右递增排列

image.png
image.png

B+Tree(B-Tree变种)
非叶子节点不存储data,只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能

image.png
image.png
数据页大小

show global status like 'innodb_page_size';
bigint  8字节 

16*1024/(8+6)= 1170    非叶子节点一行可以放1170个元素
三层高度的树 可以存放 1170*1170*16=21902400    大概2000万个行

MyISAM索引实现(非聚集)
MyISAM索引文件和数据文件是分离的，数据.MYD+结构.frm+索引.MYI三个文件

image.png

InnoDB索引实现(聚集)
数据文件本身就是索引文件
表数据文件本身就是按B+Tree组织的一个索引结构文件
聚集索引-叶节点包含了完整的数据记录
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

image.png

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

image.png

为什么InnoDB表必须建主键，且推荐使用整型的自增主键索引
为什么InnoDB表必须建立主键？
如果不建立主键
会从第一列开始，选择所有元素都不相等的一列作为索引，来组织B+树
如果选不到所有元素都不相同的列，则会创建隐藏列作为索引，组织B+树
浪费MySQL资源和性能
为什么推荐使用整型自增主键做索引？
整型：
在索引定位的过程中，中间经历过多次数据比较大小
整型查找过程中值比较效率高
字符串会按ASCII码，逐个字符比较，又经历多次，效率低
整型数据占用的磁盘空间小，节约空间
自增：
自增主键与索引有序的特性相吻合(索引插入时，按从左至右递增向后插入即可)，在新增主键时一般不会导致叶子节点频繁分裂以及平衡，效率高
如果非自增，若在节点中间硬插入数据，则该节点分裂，B+树还要进行平衡操作，效率低

联合索引底层数据结构
概念

指的是对一张表上的多个列进行索引
即：表上多个列加起来组成一个索引
供快速查询使用
一般不建议单表建立过多单值索引，而是建立2-3个联合索引来满足查询需要
分类
联合主键索引
联合非主键索引（不常用）
查询一行数据，当单列和索引和联合索引发生冲突时，MySQL优先选择单列索引

底层数据结构
按索引建立先后顺序，维护存储，仍是B+树结构
查找也按先后顺序逐个匹配查找，引出最左前缀原则/原理

image.png