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

为什么 MySQL 使用 B+Tree 做为索引

  • 二叉树
  • 红黑树
  • B-Tree
  • B+Tree（MySQL）
  • Hash表（MySQL）

image.png

B-Tree

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

image.png

B+Tree

  • 非叶子节点不存储数据，只存储索引（冗余），可以存放更多索引
  • 叶子节点包含所有索引字段
  • 叶子节点用指针相互连接，提高区间访问效率

image.png

MyISAM 存储引擎

  • 索引文件（MYI）和数据文件（MYD）是分开的

image.png

InnoDB 索引实现（聚集）

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

image.png
image.png

联合索引的底层存储结构

  • 所以参与索引的字段组合起来作为索引 key
  • 依次比较字段的 ASCii 码，作为排序规则

image.png