B树和B +树的订单是否有限制？

Question

在B tree和B+tree中，如果我们将订单指定为5，那么我们可以将4 keys存储在单个节点中，并将5 pointers存储为该节点。

在上述树中设置顺序有任何限制（或）其限制是无限的？

Answer 1

您可以设计一个系统，您可以从1向上选择任何顺序。如果顺序过大，则很难在节点中找到密钥，并且该树将只有1或2级深度。

例如，如果订单为1,000,000，那么在将任何节点拆分到树中的第三级之前，您需要获得一万亿条记录，并且您可能永远不会达到第四级。而且你必须在每个级别搜索一百万个密钥才能找到要去的地方。即使使用二分查找，也可以达到20个探针。

如果您选择较小的订单，那么您的搜索更小。例如，如果顺序是32，那么每个级别最多有5次搜索，使用二进制搜索来查找密钥以及接下来的位置。对此，每次向下移动一层时，都必须从磁盘读取一个新页面（如果它是一个磁盘备份的B树）。如果它在内存中，那么它的成本很低。

通常，您将设计具有固定页面大小的B树，并根据键的大小和指针的大小调整顺序。大钥匙给你一个更小的订单;小钥匙给你一个更大的订单。