数据结构B树

发布网友发布时间：2022-04-29 17:10

共2个回答

热心网友时间：2022-04-16 04:47

比如说一颗 B 树的阶为 1001（即 1 个节点包含 1000 个关键字），高度为 2，它可以储存超过 10 亿个关键字，我们只要让根节点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。

热心网友时间：2022-04-16 06:05

M为树的阶数，B-树或为空树，否则满足下列条件：
定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2（取上整）-1和至多M-1个关键字；（至少2个关键字,根节点至少一个关键字）；
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[m-1]，m<M+1；且K[i]< K[i+1] ；
7.非叶子结点的指针：P[1], P[2], …, P[m]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
从这些条件可以得出对于第一个问题
在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（5）
性质2，可知在一株高度为 2 的 5 阶 B 树中，最少有三个结点，由性质4，根最少一个关键字，第二层的两个结点，每个结点最少2个关键字，总共有最少有5个关键字。
对于第二个问题
在一棵具有15个关键字的4阶B树中，含关键字的结点个数最多是（15）
由性质4，每个结点存放至少1关键字，这样树中包含的结点数是最多的，这样有15个关键字的4阶B树中，含有关键字的结点个数最多是（15）也就好理解了