B树

B树是为磁盘或其他直接存取的辅助存取设备而设计的一种多叉平衡搜索树,类似于红黑树,但B树在降低磁盘I/O操作方面要更好一些。许多数据库系统使用B树或B树的变种来存储信息。 <!--more-->

我们知道,磁盘I/O是很慢的,因为要涉及到磁头寻道、定址和数据读取时间。寻道是一种机械运动,速度自然慢;定址的平均时间是磁盘旋转周期的一半,目前主流磁盘旋转速度是5400RPM,快一点的也是7200RPM,尽管如此,旋转一圈需要8.33ms,比内存存取时间的50ns要高出5个数量级。所以综合来说,磁盘I/O与主存I/O的差距在6~8个数量级之间。

因此我们需要尽可能的减少磁盘I/O的次数。这时候B树就出现了。一颗B树T是具有以下性质的有根树:

  1. 每个节点x具有下面属性:
  • x.n 当前存储在节点x中关键字的个数;
  • x.n个关键字本身x.key1,x.key2…x.key<sub>x.n</sub>,以非降序存放,使得x.key1<=x.key2<=…<=x.key<sub>x.n</sub>。
  • x.leaf,一个bool值,如果x是叶子节点,则为true,否则为false;
  1. 每个内部节点x还包含x.n+1个指向其孩子的指针;
  2. 关键字x.key<sub>i</sub>对存储在各子树中的关键字范围加以分割;
  3. 每个叶子节点具有相同的深度,即树的高度h。
  4. 每个节点所包含的关键字个数有上界和下界,其中下界>=2。

因为B树具有以上这些性质,所有尽管B树的基本操作和红黑树一样也是对数量级的,但B树中对数的底可能很大,这就使得B树的高度很低。如果我们令B树的根节点存储在主存上,那么对于一个高度为3,每个节点有1000个关键字的B树,最多只需要在磁盘上查找2次。而这棵树可以存储的信息达到1000<sup>3</sup>=十亿个!正因为此,B树特别适合用来做磁盘I/O。