MySql索引数据结构

Updated on with 0 views and 0 comments

一、索引定义

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

二、索引数据结构

  • 二叉树:单向递增时效果低
  • 红黑树:每个节点只能存一个数据,树太深,意味着从磁盘读取数据的次数多
  • Hash表
  • B-Tree
  • B+Tree

B-Tree

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

图片1.png

B+Tree(B-Tree变种)

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

图片2.png

mysql每页大小为16KB,查询语句:show GLOBAL STATUS like 'Innodb_page_size';
如果主键是BigInt,占8个字节,中间指针约6字节,那么一页可以存放16*1024/14 = 1170
假设数据为1KB,那么三层的树可以存放:1170*1170*16=21902400条数据。

Hash

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

MySql索引结构采用B+Tree和Hash。

三、不同存储引擎里索引的实现

MyISAM

MyISAM索引文件和数据文件是分离的(非聚集)
图片4.png

InnoDB

  • 表数据文件本身就是按B+Tree组织的一个索引结构文件(聚集)

  • 聚集索引-叶节点包含了完整的数据记录

  • 为什么建议InnoDB表必须建主键,并且推荐使用整型的自增主键?
    必须有主键才能构造出B+Tree,不设置主键会找出数据都不同的列,找不到mysql会生成一个隐藏列用来构键索引树。
    非自增的话,插入的时候性能消耗更大(会导致原来的页分开,树要重新平衡),自增的话,在页数据存满的时候,在后面新增一页即可。

  • 为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
    图片5.png

    非主键索引:叶子节点上存储的是主键,找到主键再通过主键查找数据(回表)。
    图片6.png

四、联合索引

图片7.png

以图示为例,先比较name,再比较age,最后比较position。所以可能出现左侧age比右侧age大的情况(因为先比较的name),这就是最左匹配。

where name = 'bill' and age = 30; # 走索引
where age = 30 and name = 'bill'; # 不走索引
where position = 'dev'; # 不走索引


标题:MySql索引数据结构
作者:fyzzz
地址:https://fyzzz.cn/articles/2021/02/23/1614090826245.html