前言
索引是在存储引擎层实现的。在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。根据叶子节点的内容，索引类型分为主键索引和非主键索引。
索引
假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？
- 自增主键的插入数据模式，每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。而身份证号做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
- 每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节。主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
- 典型的 KV 场景适合用业务字段直接做主键：只有一个索引；该索引必须是唯一索引。
基数（优化器选择索引时会参考基数值）：一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好。我们可以使用 show index 方法，看到一个索引的基数。基数是一个估计值，MySQL 使用采样统计的方法得到索引的基数：InnoDB 会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。当变更的数据行数超过 一定数量时，会自动触发重新做一次索引统计。
select count(*) 优化：InnoDB 是索引组织表，主键索引树的叶子节点是数据，而普通索引树的叶子节点是主键值。所以，普通索引树比主键索引树小很多。对于 count(*) 这样的操作，遍历哪个索引树得到的结果逻辑上都是一样的。因此，MySQL 优化器会找到最小的那棵树来遍历。在保证逻辑正确的前提下，尽量减少扫描的数据量，是数据库系统设计的通用法则之一。
唯一索引和普通索引在查询性能上差别不大，在插入/更新性能上，如果相关数据页不在内存中时，还需将相关数据页加载到内存以判断是否违反了唯一性约束。
索引
《MySQL实战45讲》索引是在存储引擎层实现的
- 哈希表这种结构适用于只有等值查询的场景
- 有序数组索引只适用于静态存储引擎，，在需要更新数据的时候就麻烦了
- 二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。原因是，索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
为什么是B+树——B+树的逻辑结构
查询需求：
- 基本查询：即根据主键查询
- 范围查询
- 前缀匹配模糊查询
- 排序和分页
每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上。
InnoDB存储B+Tree节点的方式确实非常精巧，MyISAM主要是记录了主键与对应记录地址（偏移）的映射关系。
B+树的物理结构——按页批量读写索引数据
与操作系统操作磁盘块的逻辑基本一致，操作时以块/页为单位，而不是直接从磁盘上读取记录。事实上，哪怕是访问内存，os也从未按字节读取过数据， 全部是按批量方式读取。
| 读取过程 | 写回磁盘 | ||
|---|---|---|---|
| 操作系统读取磁盘块 | 判断目标数据所在的磁盘块是否在内存（对应的缓冲块），若在则修改数据，不在则读取磁盘块到内存。 | 操作系统负责将缓冲块同步到磁盘上。修改的缓冲块称为脏块，操作系统会根据脏块的占比决定同步到磁盘期间，是否继续响应用户操作。 | 磁盘块有超级块和一般数据块的不同，不准确的说，超级块的数据加载到磁盘，刚好是一个superblock list、inode list |
| innodb引擎读取页 | 类似 | mysql有专门线程负责将脏页（有改动的页）写入到磁盘。因为redo 日志的存在，msyql会根据redo log的剩余空间占比决定在master thread中同步还是异步 将脏页写入到磁盘。 | 数据页组织在一起刚好是一个B+Tree |
- 有些文件格式（二进制文件），必须整体读取才能解析和展示，有些（主要是文本文件）则可以一部分一部分的解析和展示，比如txt。
- 有些文件格式，在内存的数据结构与磁盘一致。有些则需要转换后写入到磁盘上。
读取记录，一次读取一页，还带来一个好处，一个页的数据结构是一个整体，支持复杂的数据结构。假设一个记录10byte，无需页offset 0~9就是第一条记录，offset10~19是第二条记录（以前我就是这么想的），即用链表而不是位置维持数据的有序性。
这其实解决了笔者一直以来的一个困惑：假设一个数据库表的主键按1~1亿分布，我先插入一条主键=1的记录，再插入主键=1000的记录，再插入主键从2~100的记录。无论采用何种索引方式，每次插入，都意味着数据文件或者索引文件中数据记录的移动，操作起磁盘来就不太高效。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。在mysql中，将一个B+Tree节点的大小设为等于一个内存页，这样每个节点只需要一次I/O就可以完全载入。B-Tree中一次检索最多需要h（树的高度）-1次I/O（根节点常驻内存）。
B+树的物理结构——如何映射逻辑结构
| 逻辑结构 | 物理结构 |
|---|---|
| 非叶子节点 | 索引页 |
| 叶子节点 | 数据页 |
File Header 比较重要的几个字段
| 名称 | 大小 | 描述 |
|---|---|---|
| FIL_PAGE_PREV | 4 | 该页的上一个页 |
| FIL_PAGE_NEXT | 4 | 该页的下一个页 |
| FIL_PAGE_LSN | 8 | 该页最后被修改的LSN |
| FIL_PAGE_TYPE | 2 | 该页的类型，0x45BF为数据页 |
Page Header 比较重要的几个字段
| 名称 | 大小 | 描述 |
|---|---|---|
| PAGE_LAST_INSERT | 2 | 最后插入记录的位置 |
| PAGE_N_RECS | 2 | 该页中记录（User Record）的数量 |
| PAGE_LEVEL | 2 | 该页在索引树中位置，0000代表叶子节点 |
数据页存放的是完整的每行的记录，而在非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量（页号），而不是一个完整的行级录。
Page 与 Page 之前组成双向链表（PS：貌似只有同级的页由双向链表关联），页按照主键的顺序排序，这样page 与page 可以在磁盘上隔的好远，但逻辑上是连续的。
B+树的物理结构——页的写入与读取
按页的方式进行内存和磁盘的交互，并且几个页组织在一起刚好是一个完整的数据结构（B+Tree），在内存中改变B+Tree的操作负担不大，然后有一个周期性的机制将页刷新回磁盘。
查询时
- 树的高度一般是2~4，假设树的高度是3，则page level=2 即表示根节点。先加载根节点，然后按需加载下一个page level的页 直到叶子/数据页。
- B+Tree索引本身并不能直接找到具体的一行记录，只能找到该行记录所在的页。
- 数据库把页载入到内存中，然后通过Page Directory（存放着行级录在页内的相对位置）再进行二分查找
《MySQL实战45讲》当内存数据页跟磁盘数据页内容不一致的时候，我们称这个内存页为“脏页”。内存数据写入到磁盘后，内存和磁盘上的数据页的内容就一致了，称为“干净页”。平时执行很快的更新操作，其实就是在写内存和日志，而 MySQL 偶尔“抖”一下的那个瞬间，可能就是在刷脏页（flush）。什么情况会引发数据库的 flush 过程呢？
- InnoDB 的 redo log 写满了。这时候系统会停止所有更新操作，把 checkpoint 往前推进，redo log 留出空间可以继续写。checkpoint 可不是随便往前修改一下位置就可以的，需要将两个点之间的日志，对应的所有脏页都 flush 到磁盘上。
- 系统内存不足。当需要新的内存页，而内存不够用的时候，就要淘汰一些数据页，空出内存给别的数据页使用。如果淘汰的是“脏页”，就要先将脏页写到磁盘。
- MySQL 认为系统“空闲”的时候，刷一点“脏页”
- MySQL 正常关闭
你要正确地告诉 InnoDB 所在主机的 IO 能力（innodb_io_capacity），这样 InnoDB 才能知道需要全力刷脏页的时候，可以刷多快。此外，innodb 会根据脏页比例（innodb_max_dirty_pages_pct） 和 redo log 写盘速度 来计算 刷盘速度。MySQL 中的一个机制（innodb_flush_neighbors具体控制），可能让你的查询会更慢：在准备刷一个脏页的时候，如果这个数据页旁边的数据页刚好是脏页，就会把这个“邻居”也带着一起刷掉；而且这个把“邻居”拖下水的逻辑还可以继续蔓延/连坐，也就是对于每个邻居数据页，如果跟它相邻的数据页也还是脏页的话，也会被放到一起刷。找“邻居”这个优化在机械硬盘时代是很有意义的，而如果使用的是 SSD 这类 IOPS 比较高的设备的话，建议你把 innodb_flush_neighbors 的值设置成 0。
为什么SELECT * 效率低
为什么大家都说SELECT * 效率低 其中一个原因是非聚簇索引/辅助索引。
有一个表为t(a,b,c,d,e,f)，其中，a为主键，b列有索引。那么，在磁盘上有两棵 B+ 树，即聚集索引和辅助索引（包括单列索引、联合索引），分别保存(a,b,c,d,e,f)和(a,b)，如果查询条件中where条件可以通过b列的索引过滤掉一部分记录，查询就会先走辅助索引，如果用户只需要a列和b列的数据，直接通过辅助索引就可以知道用户查询的数据。
如果用户使用select *，获取了不需要的数据，则首先通过辅助索引过滤数据，然后再通过聚集索引获取所有的列，这就多了一次b+树查询，速度必然会慢很多。
由于辅助索引的数据比聚集索引少很多，很多情况下，通过辅助索引进行覆盖索引（通过索引就能获取用户需要的所有列），都不需要读磁盘，直接从内存取，而聚集索引很可能数据在磁盘（外存）中（取决于buffer pool的大小和命中率），这种情况下，一个是内存读，一个是磁盘读，速度差异就更显著了，几乎是数量级的差异。