MENU

B-树(2):应用及其拓展

系列文章目录

B-树(1):定义及其代码实现
B-树(2):应用及其拓展

一:应用领域

B-树与其它二叉树最大的不同,就是其可以拥有多余2个的子结点。这也正是B-树被应用于文件系统和数据库底层实现的重要原因。

我们再回顾下B-树的性质:

  1. 所有的叶子结点在同一层;

  2. 每棵 B - 树有一个 Minimum Degree,称其为 t;

  3. 除了根结点,其余每个结点至少包含 t-1 个 keys,根结点可以只包含 1 个 key;

  4. 每个结点(包括根结点)最多包含 2t-1 个 keys;

  5. 一个结点的孩子指针数等于这个结点的 keys 数 + 1;

  6. 每个结点的 keys 都按升序排列;

  7. 对于每个 key,其左边孩子结点的所有 keys 都小于它,右边孩子结点的所有 keys 都大于它。

对于一棵结点数为$n$的B-树,每一个结点的孩子指针数范围为$[t-1, 2t-1]$,所以树的高度在$[log_{t-1}n, log_{2t-1}n]$。那么当$n=10,000,000,000,t=512$时,只需要小于$4$次即可定位到该结点,然后再采用二分查找即可找到要找的值。

我们计算机的主存基本都是随机访问存储器(Random-Access Memory,简称RAM),它分为两类:静态随机访问存储器(SRAM)和动态随机访问存储器(DRAM)。SRAM比DRAM快,但是也贵的多,一般作为CPU的高速缓存,DRAM通常作为内存。

我们使用更多的是磁盘,磁盘能够保存大量的数据,从GB到TB级,但是它的读取速度比较慢,因为涉及到机器操作,读取速度为毫秒级,从DRAM读速度比从磁盘度快10万倍,从SRAM读速度比从磁盘读快100万倍。下面来看下磁盘的结构:

如上图,磁盘由盘片构成,每个盘片有两面,又称为盘面(Surface),这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴(Spindle),它使得盘片以固定的旋转速率旋转,通常是5400转每分钟(Revolution Per Minute,简称RPM)或者是7200RPM。磁盘包含多个这样的盘片并封装在一个密封的容器内。上图左,展示了一个典型的磁盘表面结构,每个表面是由一组成为磁道(Track)的同心圆组成的,每个磁道被划分为了一组扇区(Sector),每个扇区包含相等数量的数据位,通常是512子节,扇区之间由一些间隔(Gap)隔开,不存储数据。

现在来看下磁盘的读写操作:

如上图,磁盘用读写头来读写存储在磁性表面的位,而读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂,驱动器可以将读写头定位到任何磁道上,这称之为寻道操作。一旦定位到磁道后,盘片转动,磁道上的每个位经过磁头时,读写磁头就可以感知到位的值,也可以修改值。对磁盘的访问时间分为寻道时间,旋转时间,以及传送时间。

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,因此为了提高效率,要尽量减少磁盘IO操作。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。预读的长度一般为页(Page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页的大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

文件系统及数据库系统的设计者利用了磁盘预读原理,将一个结点的大小设为等于一个页,这样每个结点只需要一次IO就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

每次新建一个结点时,直接申请一个页的空间( 512或者1024),这样就保证一个结点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,这样就实现了一个结点只需一次IO操作。

二:B树的拓展

2.1 B+树

B+树是B树的变体,也是一种多路搜索树,其定义基本与B树相同,除了:

  1. 非叶子结点的孩子指针与keys数目相同;

  2. 各层结点中的keys均是下一层相应结点中最小的key(或最大的key);

  3. 为所有叶子结点增加一个链指针(key_pointer);

  4. 所有keys都会在叶子结点出现;

相比B树,B+树更适合用于实现文件存储和数据库。这主要基于以下两点:

  1. B+树的磁盘读写代价更低

    因为B+树的所有keys终究都会出现在最底层的叶子结点,所以对于非叶子结点,我们只需存储"基于比较所用的关键字"即可(仅仅作为索引),相比B树,一个结点可以存储更多的keys,也就是说,IO读写次数降低了。

  2. B+树的查询效率更稳定

    由于非叶子结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

2.2 B*树

B*树是B+树的变体,其定义基本与B+树相同,除了:

  1. 为所有非叶子结点增加指向兄弟结点的指针;

  2. 非叶子结点的keys数提高到至少$2/3$,即块的最低使用率为$2/3$(代替B+树的$1/2$)。

考虑分裂操作,

B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中$1/2$的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制$1/3$的数据到新结点,最后在父结点增加新结点的指针。

所以,B*树分配新结点的概率比B+树要低,空间使用率更高。

2.3 总结

通过以上介绍,大致将B树,B+树,B*树总结如下:

B树:有序数组+平衡多叉树,数据存在于非叶子和叶子结点上;

B+树:有序数组链表+平衡多叉树,数据只存在于叶子结点上;

B*树:一棵丰满的B+树。

三:结后语

最后,就B树的叫法作些补充。

  • B-Tree,也称"B-树","B树",读作"B 树"。注意里面的"-"不是"减"的意思,而是"杠"的意思。从不存在"B减 树"的叫法,你所听到的"B减 树",其实就是"B 杠 树",但为了叫起来顺口,直接叫"B 树"更佳。

  • B+ Tree,(也可以写作"B+ - Tree",读作"B加 杠 树"),读作"B加 树";

  • B* Tree,(也可以写作"B * - Tree",读作"B星 杠 树"),读作"B星 树"。

四:参考文献

标签: B树, B+树, B*树
返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码
添加新评论

1 条评论
  1. 文章不错支持一下吧