B-树

来自计算思维百科
跳转至: 导航搜索
B-树1.png

计算机中存储数据的方法有两种,一种是存在内存,一种是存在磁盘。在大规模数据存储时,一般都存储在外存磁盘中,而在外存磁盘中读取/写入数据是一块一块进行的,当读取/写入块(block)中某数据时,首先需要定位到磁盘中的某块,如何有效地查找磁盘中的数据,需要一种合理高效的外存数据结构。B-tree就是为了解决这个问题的一种特殊的动态查找树。

基本概念

B-树是一种平衡的排序树,也称为m路查找树。一棵m阶B-树具有以下的性质:

(1)树中的任何一个结点最多有m棵子树;

(2)如果根结点或者是叶子结点,至少有两棵子树;

(3)除了根结点以外,所有的非叶子结点至少应有m/2棵子树;

(4)所有的叶子结点处于同一层次上,且不包括任何关键字信息;

一棵深度为m=4的4阶的B-树如图所示:

B-树2.png

要查找关键字为41的元素,首先从根结点开始,将41与A结点的关键字29比较,因为41>29,所以应该在C指向的子树内查找。将41与结点C中的关键字逐个比较,因为有41<42,所以应该在F指向的子树内查找。将41与结点F中的关键字逐个进行比较,在结点F中存在关键字为41的元素,因此查找成功。在这个过程中,每个节点就是磁盘存储中的一个块数据,通过这个树结构,可以很快找到需要的数据。

应用范围

B树是一种大规模数据存储访问的有效方法,经常用于数据库、磁盘存储中。

应用案例

应用1- 找人

案例:市公安局想找小明,他们首先要确定小明属于哪个区,然后是哪个街道,然后是哪个小区,哪个楼哪个门号。在这个过程中,全市的人口已经通过区、街道、小区划分为一个一个的小块,这些小块构成一个树状结构,只要找到小明所在的一个小块,找到小明就很快了,这就是B-树的思想。

可以体现的计算思维

B-树将计算机外存文件系统,磁盘读写,动态索引等的结构模型抽象的表达出来,体现了计算思维的抽象特点。