B-tree的性能

B-tree的性能

B-tree有以下特性：
1、关键字集合分布在整棵树中；
2、任何一个关键字出现且只出现在一个结点中；
3、搜索有可能在非叶子结点结束；
4、其搜索性能等价于在关键字全集内做一次二分查找；
5、自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：
其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！