mysql索引底层数据结构与算法

mysql索引底层数据结构与算法

mysql索引底层数据结构与算法

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

索引数据结构

• 二叉树
  • 因为是二叉树，极端情况下构建的树会变成链表结构，同样的，当数据量很大时，构建的二叉树深度过大，不利于查找
• 红黑树
  • 虽然平衡了，但因为每一层所存储的节点个数不多，当数据量很大时，树的深度过大，查找效率很低
• Hash表
  • 对索引的key进行一次hash计算就可以定位出数据存储的位置
  • 很多时候Hash索引要比B+树索引更高效
  • 仅能满足”=“,”IN”，不支持范围查询
  • hash冲突问题
• B树
  • 叶节点具有相同的深度，叶节点的指针为空
  • 所有索引元素不重复
  • 节点中的数据索引从左到右递增排列
• B+树
  • 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点用指针连接，提高区间访问的性能

MyISAM存储引擎索引实现

MyISAM索引文件和数据文件是分离的（非聚集）

InnoDB索引实现（聚集）

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