B+树索引结构：

为什么使用B+Tree索引

1. 适合做索引的数据结构特点

1. 可排序的；可以利用二分搜索：AVL树、B树、B+树、B*树
2. 查询时节点尽可能的少，降低IO，即多路搜索更佳：B树、B+树

2. 对比AVL树、B树、B+树

• AVL树、B树都存在数据量增大，树高过高、回溯查找的问题；
• B树不可范围查询；
• B+树非叶子节点全部存储索引，能容纳更多索引；
• B+树的叶子节点包含全量索引；因此每次找到叶子节点，就可以获取数据；而B树每个节点都含有数据，遍历时对每个索引需要进行中序遍历(左-根-右)的方式保证顺序；

B+树目前来看是最优解：

• 索引高效：B+树非叶子节点只存放索引，每页能够存储更多的索引，使得索引效率很高；
• 大量减少磁盘IO：大部分的表结构，只需要建立3层B+树，最多只需要三次磁盘IO；
• 有序，支持范围查找：叶子节点间是双向链表连接，叶子节点中具体的记录间是单向链表；

3. B+树数据索引过程

1. 将Page1加载进内存中，发生一次磁盘IO；
2. 在内存中使用二分查找，确定索引列的位置，通过指针，找到下一个节点；
3. 将下一个节点加载进内存，发生一次磁盘IO；以此类推；
4. 直到最后找到叶子节点，加载进内存，发生一次磁盘IO，并找到索引对应的数据，读取数据； 因此三层B+树仅需三次磁盘IO，就能锁定数据；一般的表3层足矣；

4. B+树存储数据量计算

假设：非叶子节点只考虑 记录头和索引

• 索引列为BIGINT，占用8字节；
• 每条数据假设占用
  1KB
  ，一页存放16条数据； 那么：
• 单页的索引数量 = 16KB / (记录头6字节 + 索引列占用大小8字节) 一页索引量：
  16KB / 14Byte = 1170 个
• 2层索引量为：
  1170 x 1170 = 1368900 个
• 3层B+树总数据量为：
  1170 x 1170 x 16 = 21,9002,400 个
  所以：
• 使用
  8 byte
  大小的索引，一颗B+树能够存放2000万+的索引；
• 如果索引更大、或数据量更大，则有可能构建出第4层B+Tree；
• 每多出一层，就增加IO的代价，降低索引效率；

5. B+Tree索引特点

1. 每一个索引会构建一颗B+树，即一个索引页，每张表都最少有一个；
2. 索引页默认大小：16K，由
   innodb_page_size
   设置；索引页非操作系统PageCache的一页，通常为多页PageCache；
3. B+树节点包括：叶子节点、非叶子节点；
   • 非叶子节点：存储当前B+树的索引信息；
   • 叶子节点：存放具体的记录；记录间是单向链表，页间是双向链表；
4. 数据的有序性：
   • 节点内：数据按照索引列有序排序；（二分搜索查找）
   • 节点间：通过双向链表保证顺序；（保证顺序、逆序都可以遍历）
   • 但物理存储不连续，内存连续不能满足高效插入；
5. 索引的类型：
   • 聚簇索引：非叶子节点存放主键，叶子节点存放完整数据；
   • 二级索引：非叶子节点存放索引列，叶子节点仅存放主键，整个二级索引树来看，包含：索引列 + 主键；

索引分类

聚簇索引 Clustered Indexes

非叶子节点为主键、叶子节点包含全量数据；

• 一张表有且只有一个主键；没有显示设置主键，InnoDB会创建一个隐藏的row-id为聚簇索引
• 主键意味着全量数据的B+树；
• 新增数据时，根据主键进行插入，并维护主键索引树；
  • 当主键递增，则每次插入在树的末端，此时索引的维护代价小；
  • 当主键乱序，每次插入都可以在任何地方，当单数据页的数据过大，会发生页分裂，导致索引维护的代价很大；

辅助索引 Secondary Indexes

聚簇索引外的索引，统称为辅助索引；

• 非叶子节点包含：索引列；
• 叶子节点仅包含：主键；
• 如果查询结果需要索引列之外的数据，先查询到主键，再到主键B+树中查询其余数据(此过程为：回表)

1. 唯一索引

对某个或多个列创建唯一索引，则该列或多个列的值在整张表中保证唯一；

唯一索引效率高，因为不会有重复数据，在唯一索引B+树中，唯一的值锁定唯一的记录；

唯一索引的等值查询，在EXPLAIN中体现为：const；

2. 联合索引

联合索引结构：

• 多个索引列，以Tuple的形式存储；
• 从左向右，先以首个索引，进行排序；前一个索引相同的情况下，再以后一个索引排序；（联合索引有最左前缀匹配原则）

全文索引

TODO