tree - 基于 M 和 L 以及基于插入和删除顺序的 BTree 复杂度

Question

取决于 M = 键数和 L = 叶数的 BTree 的大哦是多少？

BTree如何处理顺序删除和逆序删除？

我正在分析 M 和 L 以及在 BTree 中插入和删除事物的方式如何确定运行时。

Answer 1

B-trees 始终保持完美平衡，因此以相反顺序删除将与按顺序删除相同，并且始终从同一级别（最深级别）开始。

根据 B-tree 实现，操作将在 O(log(m) * log(l)) 时间或 O(m * log(l)) 时间内发生。后者适用于已知的小 m 值，因为在 5 个左右元素的数组中进行二进制搜索并不值得。