文章目录

说明：

用于在磁盘上查找的树。应用于MySQL。

特性：

  1. <mark>数据项</mark>存储在<mark>树叶</mark>上。
  2. <mark>非叶节点</mark>存储直到<mark>M-1个关键字</mark>以指示搜索的方向；关键字i代表子树i+1中的最小的关键字。
  3. 树的根或者是一片树叶，或者其儿子数在2和M之间。
  4. 除<mark>根外</mark>，所有<mark>非树叶</mark>的<mark>节点</mark>的<mark>儿子</mark>数在[M/2]和M之间。
  5. 所有的树叶都在相同的深度上并且有[L/2]和L之间个数据项。

M&L

M：<mark>树的最大节点数</mark>，或者说最大关键字数+1。
L：叶上的<mark>数据项的最大长度</mark>。