B Tree

目录

1 概述

相比于内存, 访问磁盘/磁带等块设备时, 大块数据读写有更好的性能. 为高效使用这类设备, 应组织数据结构, 将多份数据放入一个块中. B树是解决此问题的算法统称, 具体实现时, 会基于应用场景进行优化, B+ Tree(WIKI)和\(B^*\) Tree(WIKI)是典型代表.

关于磁盘性能特征, 请访问磁盘测试数据.

2 应用

B树(或其变形)广泛应用于有大量元数据需要保存到外部存储介质的应用场景, 例如文件系统, 数据库, 以及存储自精简/压缩/重删等特性中.

3 分析

3.1 定义

读过资料中, B树最完整清晰定义来自TAOCP:

1970年, R.Bayer和E.McCreight发现了一种利用多路树分支进行外部查找的新方法, 马克.考夫曼也几乎在同一时间独立地发现了这一方法(未发表). 他们的思想基于一种被称为B树的通用新型数据结构, 有可能利用相对简单的算法来查找和更新大型数据文件, 并能在最差情况下保证效率.

\(m\)阶B树是满足以下性质的树:

  1. 每个节点最多有\(m\)个子节点;
  2. 除了根节点及叶子外, 每个节点至少有\(m/2\)个子节点;
  3. 根节点至少有\(2\)个子节点(除非它是一个叶子);
  4. 所有叶子都出现在同一级别, 并且不携带任何信息;
  5. 具有k个子节点的非叶节点包含\(k-1\)个键.

R.Bayer和McCreight仅考虑了\(m\)为奇数的情景, 因此m阶B树实际指\(2m+1\)阶B树.

B树插入节点导致分割时, 是由顶部向上生长的, 而不是在底部向下延伸, 这是因为 B树仅在分割根节点时才增高. 这正是此思想的美妙之处.

3.2 运行时间上限

给定\(m\)阶B树, 假定存在\(N\)个键, \(N+1\)个叶子出现在\(l\)级, 则 \(1, 2, 3, \dots{}\)级上的节点数至少为 \(2, \lceil{}m/2\rceil, \lceil{}m/2\rceil^2, \dots{}\) 因此 \[N+1 \ge 2\lceil{}m/2\rceil^{l-1} \] \[l \le 1+log_{\lceil{}m/2\rceil}(\frac{N+1}{2})\] 在\(N=1999 998, m=199\)时, \(l\)最多为3, 根常驻内存, 因此最多两次读盘.

插入一个新的节点时, 可能必须分割多达\(l\)个节点, 但构造整颗树时, 发生的总分割次数就是树中内部节点总数减去\(l\), 所以分割节点的平均数要少很多. 如果有\(p\)个内部节点, 则至少有\(1+(\lceil{}m/2\rceil{}-1)(p-1)\)个键. 因此 \[p \le 1 + \frac{N-1}{\lceil{}m/2\rceil{}-1}\] 可知, 在构造一个由\(N\)个键组成的树时, 每做一次插入, 需要分割节点的平均次数少于\(\frac{1}{\lceil{}m/2\rceil-1}\).

3.3 改进与变形

4 B树实现

B树需要实现创建, 插入, 删除, 搜索, 销毁操作. 参考代码<uncompleted>

5 外部链接