- 每个节点对多 m-1 个关键字
- 根节点最少可以只有 1 个关键字
- 非根节点至少有 m/2 个关键字
- 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
- 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
- 每个节点都存有索引和数据，也就是对应的 key 和 value。
B+树
- 根节点至少一个元素
- 非根节点元素范围：
m/2 <= k <= m-1
- 非叶子节点不存储数据，只存储索引，数据都存储在叶子节点。
- 对于一个非叶子节点，左子树的 key 都小于它，右子树的 key 都大于它。
- 每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依赖关键字的大小顺序连接。
- 父节点存有所有子树第一个元素的索引。
B树和B+树的区别
- B 树的每个节点都存储数据，B+ 树非叶子节点存索引，叶子节点存数据。
- B 树的叶子节点不一定在同一层，B+ 树的叶子节点都在同一层，通过链表连接。
- B 树的所有节点的 key 不重复，而 B+ 树的叶子节点的 key 可以重复。
MySQL 为什么选择 B+ 树
- 相对于 B 数据来说，因为非叶子节点不存储数据，就能够存储更多的索引了，可以使 B+ 树的高度比 B树低，减少 I/O 次数。
- B+ 树的所有叶子节点都是通过指针相连的，顺序遍历和范围查询很便利。