索引机制

B+树索引：

1、平衡查找树，叶子节点存放数据，非叶子节点存放索引键值数据

2、高扇出性：树的高度一般在2-4层【在查找某一键值的行记录时最多只需要2-4次IO操作】

3、B+树索引并不能找到一个给定键值的具体行，B+树索引能找到的只是被查找数据所在的页

4、B+树索引分为聚集索引【主键】和辅助索引，InnoDB在物理层面的索引只有两种：聚集索引【聚簇索引】和非聚集索引【非聚簇索引】

5、B+树的中间节点可以找到要查找的所有数据页

数据页是MySQL抽象出来的数据单位，是InnoDB管理的最小单位

磁盘文件中存放了很多数据页，每个数据页里存放了很多行数据。

缓冲池和磁盘之间的数据交换的单位是数据页，包括从磁盘中读取数据到缓冲池和缓冲池中数据刷回磁盘中【磁盘中存放的数据页的大小是16KB】

聚集索引

1、每张表只存在一个聚集索引，聚集索引的叶子节点存放着对应的数据页

2、聚集索引的存储并不是物理连续的，而是逻辑上连续的，数据页通过双向链表链接；同时每个数据页的记录也是通过双向链表进行维护的，同样是逻辑上有序；

3、聚集索引表记录的排列顺序与索引的排列顺序一致，所以聚集索引Crud速度快

4、查询优化器倾向于采用聚集索引；聚集索引在排序查找和范围查找时，查询优化器能够快速发现某一段范围的数据页需要扫描

5、在叶子节点获取数据是顺序读【顺序读在IO层面通常更加高效，因为它可以利用操作系统的块设备层对连续块的高效处理机制】

非聚集索引【辅助索引】

1、每张表可以有多个非聚集索引，非聚集索引的键值顺序与数据的物理存储顺序无关，叶子节点并不包含行记录的所有数据，而是对应数据页的聚集索引键和数据页的指针

2、辅助索引的存在并不影响数据在聚集索引中的组织

3、当数据被插入或更新时，非聚集索引需要先修改索引结构，再更新数据页。因此，非聚集索引的插入和更新操作可能比聚集索引更耗时

非聚集索引获取数据有两种方式：离散读和顺序读

离散读主要取决于数据页在磁盘上的物理布局以及查询访问的数据页是否连续

1、如果聚集索引中的数据页是连续存储的，并且查询访问的数据页也是连续的，那么就可以通过顺序读来高效地获取数据；通过辅助索引查找数据时，InnoDB存储引擎会遍历辅助索引并通过叶子节点获取聚集索引的主键值，然后通过聚集索引找到对应的数据页

2、如果查询访问的数据页在磁盘上是不连续的，或者数据页没有被缓存在InnoDB的缓冲池中，那么就会发生离散读。离散读会增加IO操作的复杂性和成本，因为数据库需要频繁地在不同的数据页之间进行跳转

3、当查询匹配到非聚集索引的一个或多个指针时，数据库需要根据这些指针去查找实际的数据页。这些指针可能指向磁盘上相隔较远的位置，从而导致数据库需要进行多个离散的IO操作来读取数据页

4、查询范围较大：当执行范围查询（如WHERE column_name BETWEEN value1 AND value2）时，非聚集索引可能需要访问多个条目，每个条目都指向一个不同的数据页。这种情况下，数据库需要读取多个离散的数据页来满足查询条件

索引最常见的数据结构：哈希表，有序数组，搜索树

哈希表：数组+链表实现，优点增加较快，缺点：无需插入数据，区间查询较慢，场景：等值查询[=，in]

有序数组：优点：等值查询和范围查询性能较好，缺点：增加数据成本较高，需要移动大量数据，适用场景：静态存储引擎

搜索树：查询效率高，需要保证树的平衡性，保证时间复杂度O(log(N))

为了减少一个查询读取磁盘的次数，就必须让查询过程访问尽量少的数据块，那么我们就不能使用二叉树，而是使用N叉树，这里的N叉树的N取决于数据块的大小，树根的数据块总是在内存中

索引是在存储引擎层实现的，并没有统一的索引标准，不同存储引擎的索引工作方式是不一样的

InnoDB的索引模型

每一个索引在InnoDB中都对应一颗B+树

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表，InnoDB使用B+树索引模型，所以数据都是存储在B+树中的

主键分为主键索引和非主键索引

主键索引的叶子节点存的是整行数据，在InnoDB中，主键索引又称聚簇索引

非主键索引的叶子节点内容是主键的值，在InnoDB中，非主键索引又称为二级索引

主键索引和普通索引的区别？

例如一张表T中主键为id，普通索引为k

Select * from T where id = 500;使用主键查询，只需要搜索ID的B+树

Select * from T where k = 5;通过普通索引查询，需要先搜索k索引树，得到ID的值，然后再到ID索引树搜索一次，这个过程称为回表

回到主键索引树搜索的过程，称为回表

索引维护

B+树为了维护索引的有序性，在插入新值的时候需要做必要的维护。

页分裂：如果某个节点所在的数据页满了，根据B+树算法，这个时候需要申请一个新的数据页，然后挪动部分数据过去，这种情况下，性能降低，降低数据页的利用率

页合并：当相邻两个页由于删除了数据，利用率很低，会将数据页做合并，合并的过程，可以认为是分裂过程的逆过程

由于每个非主键索引的叶子节点上都是主键的值，如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果使用整形做主键，则只要4个字节，使用长整型则是8个字节

主键长度越小，普通索引的叶子节点越小，普通索引占用的空间就越小

自增主键的优点：每次插入一条新纪录，都是追加操作，不涉及挪动其他记录，也不会触动叶子节点的分裂

业务逻辑字段做主键的缺点：无法保证有序插入，这样写数据成本相对较高

那些场景应该使用自增主键：

从性能和存储空间考虑，自增主键往往是合理的选择，非主键索引占用的空间较小

那些场景适合用业务字段直接做主键？

只有一个索引，且必须是唯一索引，典型的K-V场景，不需要考虑其他索引的叶子节点大小

索引覆盖：需要查找的字段，刚好在使用的索引树上

索引覆盖可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段

索引覆盖-案例一：非聚集索引不包含整行记录的所有信息，因此非聚集索引的大