B-树 动机与结构

Ps.我们遵循从感性到理性的认知顺序来逐步探索B-树的奥秘,之前经常说的value这里用key(关键码)指代,因为可能存的是字符串,说是value就不合适了。

(多图预警!!!建议在WI-FI下观看) 

虽然迄今为止我们所看到的查找树皆为二叉树,但还有另一种常用的查找树与此相异,名为B- 树,又叫B树。下面是B-树的基本信息

B-树 动机与结构

在物理上,B-树的每一个节点都可能包含多个分支,然而后面会看到,从逻辑上讲,它依然等效于此前所介绍的二叉查找树,因此我们依然把它归入搜索树的范畴。那已经有了之前那么多的种类,设计和实现B-树的动机何在呢?B树最初也是最主要的功能,在于弥合不同存储级别之间在访问速度上的巨大差异——也就是实现高效的IO。先让我们穿越到37年前,那时Bill Gates的一句话曾经被很多人当作笑柄。

B-树 动机与结构

因为他在那时曾经断言640KB也就是dos的基本内存容量,已经足以满足任何实际应用的需要了。虽然这话有点武断,但在学习完B树以后,我们一定会认为这句话实际上是千真万确的真理,因为我们有各种各样的玄学优化手段2333。

 

从某种意义上讲,我们在计算过程中能够使用的内存是在日益的变小,而不是如我们直觉一样,变得越来越大。这听起来似乎是个悖论,但原因在于需要处理的信息量级越来越大:系统存储容量的增长速度<<应用问题规模的增长速度。不妨来看这样一组统计数字

B-树 动机与结构

而我们人类所拥有的数字化信息的总量,在过去的半个多世纪中增长速度是惊人的,比如截至2010年总量以及达到Zettabyte——1后面要接210。我们知道中国的人口大致是十多亿,也就是109次方左右,分摊下去每个人都需要一个TB规模的硬盘(如果硬盘里女朋友比较多这空间还不够呢233),注意,这里我们说的还只是硬盘,是外部存储。而如果考虑内存,那这方面的压力就更大了。

不妨来进一步看一些数字,对不同年代典型的数据库规模和内存规模做个对比:

B-树 动机与结构

 

短短20年,内存规模跃升1000倍,但是数据规模则跃升了百万、千万倍。内存容量的压力其实更大了,这个压力提高了至少100倍。而如今典型的数据集已经大多以TB作为度量单位了,无论是生物分子学、医学、物理学,还是核能、气象等领域。随便举几个例子

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwxxjs.html