MySQL索引数据结构

索引的本质

索引是什么：索引是一种帮助MySQL高效获取数据的有序数据结构

索引数据结构的选择

为什么使用索引？

MySQL数据库存储数据最终以文件的形式存储在硬盘中，要读取数据需要进行文件IO操作，而每次进行磁盘IO的代价比较昂贵，索引的出现与选择最终的目标是尽可能的减少磁盘IO的次数

二叉树

如果数据单边增长，就会出现链表一样的数据结构，数的高度太高，索引IO次数无法控制

image.png

红黑树

红黑树又称为二叉平衡树，在二叉树的基础上多了一个平衡。不像二叉树极端情况下往一个方向发展，但依旧存在数据量大时树的高度无法控制，导致索引IO次数无法过高

image.png

B-Tree

在红黑树的基础上，每个节点存储多个值。

• 叶子节点具体相同的深度
• 索引元素不重复

• 节点的数据索引从左到右递增排序

  
  image.png

B+Tree

B-Tree的变种

• 非叶子节点不存在数据，只存储索引值（这样同一页可以存更多的索引）
• 叶子节点保存所有的索引字段内容

• 叶子节点用指针连接（提高区间访问的性能）

  
  image.png

在MySQL中使用B+Tree数据结构存储索引，叶子节点使用双向链表

预读：磁盘一般会顺序向后读取一定长度的数据（页的整数倍）放入内存，B+Tree的节点大小设置为一个页
MySQL中InnoDB每一页默认存储的大小为16K（通过命令：【SHOW GLOBAL STATUS LIKE 'INNODB_PAGE_SIZE'】查看），太小每次IO加载的数据量过小，太大每次IO性能有影响

计算MySQL索引B+Tree的高度（InnoDB为例）

B+Tree一个节点为一个页，一页大小为16K，页大小 = 16 * 1024 字节

非叶子节点

• 以主键索引为BIGINT为例，存储大小为8个字节，索引树的节点上除了存储key，还需要存储指针
• 指针大小在InnoDB源码中设置为6字节，合计14个字节
• 则每个节点可存储：16 * 1024 / (8 + 6) = 1170个
  叶子节点
• 假设存储一行记录的长度为1K，则一个节点可存储： 16 / 1 = 16个

数的高度为n，能存储：1170 ^ (n - 1) * 16
树的高度为2，能存储：1170 * 16 = 18720
树的高度为3，能存储：1170 * 1170 * 16 = 21902400
树的高度为4，能存储：1170 * 1170 * 1170 * 16 = 25625808000

MySQL常见的的存储引擎

MyISAM

• 不支持事务
• 支持全文索引
• 不支持外键
• 索引文件（myi）与数据文件分离（myd）
• 叶子节点存储的是数据文件的物理地址，通过物理地址在myd文件中查找具体的行记录
• 表级锁定

image.png

InnoDB

• 支持事务，四种事务
• 行级锁定：通过索引实现，全表扫描仍然会是表锁
• 支持外键
• 必须存在主键，如果没有设置主键，则取一个不为空的唯一索引作为主键索引，如果不存在MySQL隐式新增一个隐式行ID作为主键索引
• 主键索引叶子节点存储了完整的行记录
• 非主键索引叶子节点存在主键id，保证数据的一致性和节约空间

• 建议主键自增，减少数据移动

  
  image.png
  image.png

Momery

• 基于内存实现，服务器重启数据消失
• 默认实现Hash索引