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

索引的本质

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

索引数据结构有以下几种：(==Mysql 最终使用 B+ Tree==)

• 二叉树
• 红黑树
• Hash表
• B-Tree

二叉树 (第二图的时候高度会很高)

红黑树----平衡二叉树

B-Tree (一个节点可以放多个索引，一般一个节点最大16 kB)

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

B+Tree(B-Tree变种)

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段

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

  
  

MyISAM存储引擎索引实现

• MyISAM索引文件和数据文件是分离的(非聚集)

  
  

InnoDB存储引擎索引实现

• InnoDB索引实现(聚集)

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

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

• 为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？

就算没有设计主键，mysql 会自动将唯一的字段作为主键，当没有唯一字段时，后台会自己生成一个 rowid 的字段作为主键，只是看不到而已.整型是为了主键索引便于比较。自增当然也是为了让索引利于存放，比如：新增一条数据，索引直接加在后面，而不需要再去遍历索引树来判断到底该放在哪里，大大地提升了效率。

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

如果非主键索引的叶子节点也存完整的数据时，比如你更新一条数据之前需要将主键索引和非主键索引的那个数据更改完才能进行更新操作(相当于是一个分布式事物了，性能大大降低). 我们只需要通过存储的主键进行定位即可。

主键索引

非主键索引

联合索引的底层存储结构长什么样？