B Tree

定义

  • 每个结点至多拥有M棵子树(最大结点关键字个数)
  • 根结点至少拥有两棵子树
  • 除了根结点以外，其余每个分支结点至少拥有M/2棵子树
  • 所有叶子结点在同一层
  • K棵子树的分支节点存在K-1个关键字
  • 关键字ceil(M/2) - 1 <= n <= M-1

出现原因

  • 红黑树是一个二叉树，在磁盘中寻找结点需要进行更多次磁盘寻址
  • 需要一些降低层高的数据结构

B Tree与B+ Tree

  • B Tree：所有节点均存储数据
  • B+ Tree：只有叶子节点存储数据，内节点只用于索引(存储key)