索引：

1. 作用：提高查询效率
2. 索引不止存在内存中，还要写到磁盘上

常见的索引模型：

• 哈希表：适用于只有等值查询的场景（kv键值对）
• 有序数组：等值查询和范围查询场景（redis的有序集合）
• 搜索树：二叉树是搜索效率最高，大多数的数据库存储却并不使用二叉树

  [!TIP] 索引不止存在内存中，还要写到磁盘上。N 叉树（B+树）由于在读写上的性能优点，以及适配磁盘的访问模式

基础：

1. 索引中的数据页的编号不一定连续，也就是说这些页在存储空间里可能并不挨着
2. B+树中相同层次的数据页通过页结构的File Header 中的FIL_PAGE_PREV和FIL_PAGE_NEXT，组成双向循环链表
3. 每个数据页内部会维护页目录，通过分组的方式将所有用户记录分组
4. 每个数据页内部记录之间通过next_record连接，next_record记录的是下一个记录的偏移位置
5. 存储用户记录的页和存储索引的页结构FIL_PAGE_TYPE都是"FIL_PAGE_INDEX"
6. 存储索引的页里面的记录叫做目录项记录，即索引的非叶子结点
7. 存储用户记录的页里面的记录做用户记录，即索引的叶子节点
8. 存储目录项记录页中的主键值最小的那个记录的min_rec_mask值为1