B树和B+树
B树
每个节点是一个磁盘快。每个磁盘快有固定大小，可以存储多个K-V键值对。
每个磁盘快包含指向下层节点的指针，方便查找。
由于每个节点存储了更多的键值对数据，可以有效降低查找树的次数，并减少查询磁盘。
B+树
存储空间
B+树是在B树的基础上演进的。
B+树的非叶子结点是不保存数据的，仅保存键值。
在 InnoDB中页大小是固定的，在只保存键值的情况下，同一个数据页能保存更多的键值。这样就能保证整个树的层级大大降低，减少向下搜索时候的磁盘IO次数，会提高数据的查询效率。
InnoDB 中页的默认大小是 16KB。
假如每页能存储1000个数据，3层B+树就可以保存 100010001000 = 10亿条数据。
由于根结点的数据常驻内存，那么查询10亿条以内的数据只需要进行2次磁盘IO，就能找到数据所在的页。
有序存储
数据都保存在B+树的叶子节点上，而每个叶子节点对应一个页（磁盘快）。
每个单独的页会对数据进行分组，分组时选出记录最小值，维护到有序数组。每一组都是一个单向链表。
索引定位到page后，如何定位数据？
- 根据有序数组，通过
二分法查找到对应的分组。 - 根据分组中的最小记录，按照单向链表去查找数据，直到查到为止。
由于叶子节点数据的有序性，在顺序查找，排序，范围查找场景时，B+树效率会很高。
链表
不同页之间双向链表连接。
方便跨页操作，比如范围查询。
叶子节点的数据通过单向链表连接。
保证有序性，方便插入和删除。
不同点
- 存储数据方式
- B树每个节点都存放数据。
- B+树只有叶子结点存放数据。
- 存储数据层级
- 相同数量数据，B树的层级会比B+树深。
- 数据查找效率
- 由于B+树的层级会小于B树，意味着磁盘IO次数会减少。进而提高了查找速率。