【一文系列】一文掌握mysql索引底层原理
1、铺垫：几种树的介绍
第一种：二叉查找树
不适合用作数据库索引：
(1)当数据量大的时候，树的高度会比较高，查询会比较慢；
(2)每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO；
第二种：B树
特点：
(1)不再是二叉查找，而是m叉查找；
(2)叶子节点，非叶子节点，都存储数据；
(3)中序遍历，可以获得所有节点；
B树为何适合做索引？
(1)由于是m分叉的，高度能够大大降低；
(2)每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO；
第三种：B+树
B+树仍是m叉搜索树，在B树的基础上，做了一些改进：
(1)非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
(2)叶子之间，增加了链表，获取所有节点，不再需要中序遍历；
B+树比B树有更优的的特性：
(1)范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯；
(2)叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；
(3)非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引；
关于局部性原理
(1)磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘IO，提高效率(通常，一页数据是4K)；
(2)局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO；
2、聚簇索引和非聚簇索引
聚集索引
以innodb为例，在一个数据table中，它由table.frm、table.idb组成。table.frm保存表结构的定义。table.idb保存的是数据和索引。
在innodb中，既存储主键索引值，又存储行数据，称之为聚簇索引。
非叶子节点只记录KEY，叶子节点存储实际记录行。
- 同一个表中，聚簇索引 只能有一个，因为无法同时把数据行放在两个不同的地方
PRIMARY KEY 是一种典型的 聚簇索引 ，InnoDB 的 聚簇索引 具体选择策略如下：
- 默认主键索引为聚簇索引，如果没有定义主键，会选择一个唯一的非空索引来代替，如果没有这样的索引,InnoDB 会隐式定义个主键来作为聚簇索引.
聚簇索引的优点
- 数据访问更快。聚族索引将索引和数据保存在同一个B-Tree中，因此从聚族索引中获取数据通常比在非聚族索引中查找更快
- 使用覆盖索引扫描的查询可以直接使用节点中的主键值
聚簇索引的缺点
- 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置
- 二级索引的叶子节点存储的是主键的值，因此访问需要两次索引查找(回表)，而不是一次。
- 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次分裂操作。页分裂会导致表占用更多的磁盘空间。
非聚集索引
以MyISAM为例，在一个数据table中，它由table.frm、table.MYI、table.MYD组成。table.frm保存表结构的定义。table.MYI保存的是索引、table.MYD保存的是数据。在用到索引时，先到table.myi(索引树)中进行查找，取到数据所在table.MYD的行位置，拿到数据。所以MyISAM引擎的索引文件和数据文件是独立分开的，则称之为非聚簇索引。
3、索引类型
主键索引
- 不可重复，不可为空
- mysql必须有主键索引(即使不配置，也会默认有一个，用于构建B+树)
单列索引
使用字段关键字建立的索引，主要是提高查询速度
唯一索引
- 不可重复，可为空。
- NULL表示的是未知，因此两个NULL比较的结果既不相等，也不相等，结果仍然是未知
组合索引
联合索引是指对表上的多个列进行索引。联合索引也是一颗B+树，不同的是联合索引的键值数量不是1，而是大于等于2。遵循最左前缀匹配原则
全文索引
在5.6版本之前，只有 MyISAM 引擎支持全文索引，在 5.6版本后InnoDB引擎也支持全文索引，在 mysql 中全文索引不支持中文。
4、拓展
mysql页文件默认为16K，将数据放在叶子节点，则非叶子节点可以存储更多的索引值
SHOW GLOBAL STATUS like 'Innodb_page_size';
假设每行数据为1K，一页可以存放16条数据。
- 如果索引是bigint类型，占8B，指针占6B，一页可以存储16384/(8+6) = 1170个(主键+指针)
- 树高为2的话，可以保存1170 * 16 = 18720条行数据
- 树高为3的话，可以保存1170 1170 16 = 21902400.可以达到千万级别
为什么Innodb表必须要有主键，并且推荐使用整型的自增主键？
- 没有定义主键也会自动创建个主键(原因前面已经说了)
- 使用整型是为了节省空间，在16K的页容量里可以存储更多的值
- 使用自增主键是结合树的特性，减少页分裂出现的概率(其实如果使用自增id在插入新行，或者id被更新导致需要移动行的时候，也会页分裂，前面也有说到了)，如果使用的是uuid的话，每次插入都需要转ASCII进行比较大小，而且增大了页分裂的概率