索引存储结构
InnoDB 采用 B+ 树来存储索引。
B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。
在实际应用中，3 层的 B+ 树可以表示上千万的数据。
MySQL 使用 InnoDB 引擎，MySQL 默认页文件大小为 16k。
假设我们一行数据大小为 1k，那么一页存储 16 条数据，也就是说一个叶子节点能存储 16 条数据。
非叶子节点，假设主键 ID 为 bigint 类型，那么长度为 8B，指针大小在 InnoDB 引擎中的大小为 6B，一共 14B，那么一页中可以存放 16k/14B=1170 个 (主键+指针)。
也就是说高度为 2 的 B+树可以存储的数据为: 1170*16=18720 条；高度为 3 的 B+树可以存储的数据为: 1170*1170*16=21902400 (千万条数据)。
B+Tree vs BTree
- B+树中，所有的数据都存放到叶子节点中，并且可以在叶子节点上支持遍历查找。
- B 树，数据存放在叶子节点或非叶子节点中。
- 由于 B 树部分数据存放在非叶子节点中，因此每个页上可以放的索引数目降低，即相同的数据，B 树的高度要高于 B+树的高度，磁盘访问次数增多。
索引使用 B+Tree？
和 b 树、红黑树、hash 表、avl 树、二叉搜索树的比较。
- Hash 表，依赖于哈希函数，数据量大时冲突较多，适用于内存情况，不支持顺序和范围查找。
- 二叉搜索树，依赖于数据插入的顺序，如果按主键大小顺序插入，那么查找的时候就是 O (n) 复杂度。
- avl 树，为了避免二叉搜索树，进行平衡，平衡较麻烦。
- 红黑树，为了减少 avl 树的平衡。
- 这三种树都主要适用于内存，如果一个节点存放到一个磁盘块上，资源耗费多；并且不支持顺序和范围查找。
- B 树，一个节点中可以存放多个数据，适用于索引的构建。但是不支持顺序和范围查找。
- B+树，除了顺序和范围查找，由于数据都存放到叶子节点上，其他节点上就只需要存放索引就可以，如此存放的分支更多，相同的数据量，B+树能够存放的高度更低，IO 次数更少。