2-3树

这最简单的B树结构

• 2-3树的所有叶子结点都在同一层（只要是B树都满足这个条件）
• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
• 2-3树是由二节点和三节点构成的树

B树 B-tree B - > balanced

• B树的阶： 节点的最多子节点个数 ，如2-3树的阶是3 ， 2-3-4树的阶是4
• 每个节点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。在文件系统中，B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址
• B树的搜索：从根节点开始，对节点内的key (有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点，重复上述过程，直到叶子结点
• 关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据
• 搜索性能等价于在关键字全集内做一次二分查找
• 在非叶子节点也可结束搜索

B+树

B+树是B树的变体，也是一种多路搜索树

• 包含两种类型节点：索引节点（非叶子节点）和 叶子节点，非叶子节点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子节点中

• 搜索与B树基本相同，区别在于B+树只有达到叶子节点才会命中，其性能也等价于在关键字全集内做一次二分查找

• 不可能在非叶子节点命中

• 非叶子节点中存放的数据项相当于是叶子结点的索引（稀疏索引）

• 叶子节点相当于是存储数据的数据层

• 更适合文件索引系统