sql - 使用 SQL 实现 B+ 树结构

Question

我很清楚纯 sql 中现有的二叉搜索树实现，但我无法想象如何构建实现 B+ 树数据结构的数据库模型。甚至可能吗？

任何见解将不胜感激。

Answer 1

1. B+Tree 和二分查找不一样。
2. 可以在表格中使用 B+Tree 结构（假设您知道它是什么）。

是否推荐 2 值得研究，但我们公司做了很多。

在表上使用 B+Tree 的示例是：

ColId       SomeData        ParentId
------------------------------------
  1           Data 1          null
  2           Data 2          null
  3           Data 3            1
  4           Data 4            1
  5           Data 5            3

等等。这个想法是您可以通过查看父 id 找到项目 5 的父项​​。您可以制作/重用各种方便的算法来查找物品及其位置。使用具有较大增量的 ColId，例如 10 或 100 的增量，可以让您为将项目插入树中留出空间。

例如...第 5 项的父项是第 3 项。祖父项是第 1 项。任何带有 null 的都是根（起始）项...它们没有父项。

正如您可以想象的那样，搜索速度非常快，但更新或添加速度却很慢（如果您没有按照上面的建议留出空间）。如果您确实留下了空间，那么当您用完空间并且必须重写项目时，添加速度会很慢。假设您将数据传授得很好，这种情况不应该经常发生。如果是这样，那么 B+Tree 可能并不是该特定格式的理想选择。一般来说，如果对数据的大部分操作是读取/搜索/过滤等，B+Tree 结构就很好。但是如果有很多更新和添加，可能就不那么好了。

由于您的问题似乎是关于如何在 sql server 表中使用 B+Tree 格式，我将让您看看这与二进制搜索之间的区别。二进制搜索是一种用于搜索某物的算法，首先对集合进行排序，然后每次除以一半，直到找到所需的内容。B+Tree 也可用于搜索，但不同之处在于它在层次结构上运行（因此得名 Tree）。