数据结构与算法分析 8.9分
读书笔记 4.7 B-树
knightley
虽然迄今为止我们所看到的查找树都是二叉树,但是还有一种常用的查找树不是二叉树。这种树叫做B-树(B-tree)。
阶为M的B-树是一棵具有下列结构特性的树:
1.树的根或者是一片树叶,或者其儿子数在2和M之间。
2.除根外,所有非树叶节点的儿子数在取顶符号(M/2)和M之间。
3.所有的树叶都在相同的深度上。
所有的数据都存储在树叶上。在每一个内部节点上皆含有指向该节点各儿子的指针P1,P2,……,Pm和分别代表在子树P2,P3……,Pm中发现的最小关键字的值K1,K2,……,Km-1。当然,可能有些指针是NULL,而其对应的Ki则是未定义的。对于每一个节点,其子树P1中的所有关键字都小于子树P2的关键字,如此等等。树叶包含所有实际数据,这些数据或者是关键字本身,或者是指向含有这些关键字的记录的指针。B-树有多重定义,这些定义在一些次要的细节上不同于我们定义的结构,不过,我们定义的B-树是一种流行的结构。(另一种流行的结构允许实际数据存储在树叶上,也可以存储在内部节点上,正如我们在二叉查找树中所做的那样。)我们还要求(暂时)在(非根)树叶中关键字的个数也在取顶符号(M/2)和M之间。
4阶B-树更流行的称呼是2-3-4树,而3阶B-树叫做2-3树。
B-树的深度最多是xxx(参见书上P101,符号打不出来)。经验指出,从运行时间考虑,M的最好(合法的)选择是M=3或M=4。
B-树实际用于数据库系统。

B-树的一些重要概念。

注:取顶符号的解释,详见wiki:https://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E7%AC%A6%E8%99%9F

0
《数据结构与算法分析》的全部笔记 66篇
豆瓣
免费下载 iOS / Android 版客户端