多路查找树

• 2-3树
• 2-3-4树
• B树
• B+树

多叉树：

• 树的每个节点可以有超过2个子节点
• 举例：2-3树、2-3-4树、B树、B+树

概念：

• 阶数(Order)，对于一颗M阶B树，一个节点最多包含M个子节点

B树(Balanced Tree)：

• B树是多路平衡查找树的一种特殊类型
• B 是Balance的意思
• M阶B树 特点：
  • 每个节点最多包含M个子节点。
  • 根节点至少包含 2 个子节点（或者0个子节点）
  • 每个非叶节点至少包含 ceil(M/2) 个子节点；
  • 拥有 k 个子节点的非叶节点将包含 k - 1 条记录
  • 所有叶节点都在同一层中
• B树的优点：
  • 相对平衡二叉树，节点的空间的利用率更高
  • 对访问局部性原理的利用(预读机制)
• B树缺点：
  • 查询范围数据时，必须按照树的中顺遍历来访问各个节点