Innodb中各个数据页可以组成一个双向链表，而每个数据页的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在其中的记录生成一个页目录，通过主键查找某条记录时可以通过页目录使用二分法快速定位到对应的槽，再遍历槽对应分组中的记录即可快速查找到指定的记录。

1、没有索引时进行查找

我们知道数据记录存储在数据页中，数据页中的记录是一个按照主键值由小到大顺序串联的单向链表，那么如何根据主键查找对应记录呢？

（1）假设数据较少在同一个页中查找

• 以主键为查询条件： 页目录二分查找槽，遍历槽对应分组记录
• 以其他列作为搜索条件： 从Infimum记录开始依次遍历单向链表中的每条记录，比对每条记录是否符合搜索条件

（2）在很多页中查找

沿双向链表依次查找数据页，然后和(1)中相同

当数据量很大时，数据页非常多，需要遍历很多页面，带来巨大的io开销，所以我们需要快速定位页面的方案。

2、索引方案

2.1、简单的索引方案

如果我们想快速定位数据页，必须做到两点：

（1）下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
页分裂：为了保证下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的状态，需要 通过记录移动的操作，这个过程叫页分裂
（2）给所有数据页建立目录项

查找步骤：

（1）在目录项中二分查找，查找出对应主键所在的目录项，获取对应的页号
（2）在页中根据页目录二分查找槽，遍历槽对应分组记录，从而获取对应主键记录

2.2、InnoDB的索引方案

InnoDB采用用数据页存储目录项。为了区分目录项记录和用户记录，在记录头中有个record_type属性

• 0 ：普通用户记录
• 1：目录项记录
• 2：Infimum记录
• 3：Supermun记录

  新分配的数据页号可能不是连续的，即这些页在磁盘上并不相邻，IndoDB会尽量让其相邻，通过维护上一页下一页的编号维护了链表关系

由于一个数据页存储的目录项记录有限，所以需要多个页存储目录项记录，此时需要遍历目录项记录页的双向链表，于是为存储目录项记录的数据页再生成一个更高级的目录。
随着记录数的增加，目录层级也会继续增加。这个索引结构即为B+树。

B+树索引特点：
真正的用户记录都存储在B+树的叶子节点

B+树高度分析：

假设一条行记录的数据大小为1k,然后每个数据页叶子节点的数据页可以存放16条用户记录（数据页中文件头，页头，页目录等结构占用空间忽略不计）
而非叶子节点存放目录项记录的页可以存放多少目录项呢，假设主键ID为bigint类型，长度为8字节，页号为int，占4个字节，那么16kB的数据页
可以存放近千条目录项

如果B+树为1层： 16条记录
如果B+树为2层： 16 1000 = 1.6万条记录
如果B+树为3层： 16 1000 1000 = 1600万 条记录
如果B+树为4层： 16 1000 1000 1000 = 160亿条记录

所以一般B+树为1-3层，不会超过4层