c - B树和B+树的顺序有限制吗？

Question

在 B 树 和 B+tree 中，如果我们将顺序指定为 5 那么我们可以存储 4 个键 在单个节点中，并且该节点有 5 个指针。

在上述树中设置顺序有任何限制(或者)它的限制是无限的？

Answer 1

您可以按照 1 级以上的任意顺序来设计系统。如果订单太大，则很难在节点中找到键，并且树将只有 1 或 2 层深。

例如，如果顺序是 1,000,000，那么在将任何节点拆分到树中的第三层之前，您需要获取一万亿条记录，并且您可能永远不会到达第四层。而且你必须在每个级别搜索一百万个键才能找到要去的地方。即使使用二分搜索，最多也有 20 个探测。

如果您选择较小的订单，那么您的搜索量也会较小。例如，如果顺序为 32，则每个级别最多可进行 5 次搜索，并使用二分搜索来查找 key 以及下一步的位置。与此相反，每次向下移动一个级别时，您都必须从磁盘读取一个新页面(如果它是磁盘支持的 B 树)。如果它在内存中，则成本非常低。

通常，您设计具有固定页面大小的 B 树，并根据键的大小和指针的大小调整顺序。大 key 给您带来更小的订单；小 key 给您带来更大的订单。