Mysql 索引底层数据结构
索引的本质
索引是帮助MySQL高效获取数据的排好序的数据结构。
索引的数据结构
-
二叉树
定义：每个结点最多有两个子树，左子树比父节点小，右子树比父节点大。
缺点：在极端情况下，形成单边子树。
-
红黑树
定义：当左右节点深度差值俩级后，自动平衡数据，中位数当在父节点，比中位数大的数字放在右子节点，比中位数小的数字放在左子节点。实际上也是一颗二叉树。也称为二叉平衡树。
缺点：公司的数据上千万行，如果按红黑树的特征存储数据，则树的高度非常高。
-
Hash表
定义：对查找结果字段值计算hash，快速找到索引所在行的磁盘文件指针。
缺点：存在hash碰撞；无法支持范围查找。
-
B-Tree
上面说到红黑树的缺点，在B树中得到改造，讲单节点横向扩展，使得单节点可以存储更多数据。
定义：叶节点具有相同的深度，叶节点的指针为空，所有索引元素不重复，节点中的数据索引从左到右递增排列。
B+树
对B-Tree进行改造，得到一种B+Tree的概念，也称为多叉平衡树，单看一个小块也为二叉树，某一个节点元素，从左到右依次为递增的。
-
非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引;
-
叶子节点包含所有索引字段;
-
叶子节点用指针连接，提高区间访问的性能;
节点存储大小为16K，把data元素移走之后，数据将会存储的更多。存储的指为8B，指针为6B，16K/8B=1170个索引。假设树高度为3，叶子节点的元素大概是1K，大概可以放16个。1170117016=20000000个数据。
Mysql 存储引擎
MyISAM
MyISAM索引文件和数据文件是分离的(非聚集)
索引存储在tablename.myi文件中，叶子节点存储索引所在行的磁盘文件指针，根据得到的索引指针，到tablename.myd中查到行数据。
InnoDB
data元素存储的是索引所在行的其他所有字段。索引和数据存放在一个文件中，及聚集索引。
主键索引
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
InnoDB表数据文件本身就是按B+Tree组织的索引结构，如果设置了主键，那么InnoDB会选择主键作为聚集索引、如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。
使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页。避免Mysql因为频繁数据移动和分页操作造成大量的碎片。
非主键索引
data元素存储的是索引所在行的主键索引。查找是找到索引所在行的主键索引，再根据主键索引查找索引所在行数据。
联合索引
将多个字段创建联合索引，避免生成多个索引树，减少存储空间。按照逐个字段比较大小，排好序。