美文网首页
深入理解Mysql索引底层数据结构与算法

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

作者: 古飞_数据 | 来源:发表于2022-09-30 19:55 被阅读0次

索引是帮助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

相关文章

网友评论

      本文标题:深入理解Mysql索引底层数据结构与算法

      本文链接:https://www.haomeiwen.com/subject/wcmdartx.html