【学习笔记之数据库系统工程师】B-树

it2025-03-25  4

B-tree中,每个结点包含:

1、本结点所含关键字的个数;

2、指向父结点的指针;

3、关键字;

4、指向子结点的指针;

B-tree有以下特性:

1、关键字集合分布在整棵树中;

2、任何一个关键字出现且只出现在一个结点中;

3、搜索有可能在非叶子结点结束;

4、其搜索性能等价于在关键字全集内做一次二分查找;

5、自动层次控制;

其他

B-树中,所有非终端结点也就是非叶子结点,都会包含关键字。

B-树中,所有叶子结点都出现在同一层次上并且不带信息(可以看做是外部结点或查找失败的结点),层次相同也就是高度相同,从根结点到每个叶子结点的路径长度相同。

B-树中,所有非终端结点包含的关键字数量是不确定的,指向的子树个数也是不确定的。

最新回复(0)