MYSQL-索引底层实现

索引数据结构

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

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分，并且左子树小于叶子节点，右子树都大于叶子节点。

红黑树

hash表

查找单个数据速度快，但进行范围查找时，效果不好。

B-Tree

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

存储引擎

MyISAM

MyISAM 是非聚集索引(索引文件和数据文件是分离的)
.frm 表定义，是描述表结构的文件。
.MYD 数据信息文件，是表的数据文件。
.MYI 索引信息文件，是表数据文件中任何索引的数据数。

InnoDB

InnoDB 是聚集索引(索引和数据放在一起)
.frm 表定义，表结构文件
.ibd 表数据和索引的文件，该表的索引的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

联合索引底层原理