如何在B-Tree上使用隐含OR查询？

Question

我想使用b-tree进行索引，但我想不出OR查询的解决方案。

对于OR查询，我指的是类似select * from table where id介于1和5之间或id在10和15之间的查询；

如果我使用id作为b-tree中的键，那么我如何在b-tree上执行上述查询呢？

在搜索b-树时，假设小于6和大于6的键位于不同的子树上，而当搜索路径经过包含小于6的键的子树时，可以检索到1到5之间的id，但是10到15之间的id又如何呢？

我是否必须使用b+tree，当我找到指向id1的密钥时，我只需要一个接一个地扫描叶子节点，直到找到指向id15的密钥？这是不是这类查询的糟糕解决方案: select * from table where id介于1和5之间或者id介于10000000和10000005之间？

或者还有其他的解决方案吗？

非常感谢!

Answer 1

OR操作意味着需要执行两次搜索，并合并结果。

Answer 2

OR关键字是一个常见的问题。从索引的角度来看，通常最好做两次查找(例如，像UNION)。

但是，也存在例外。您的第一个示例(id介于1和5之间或id介于10和15之间)可能最好在1到15之间的一个索引查找中完成，丢弃值6到9。但是，这取决于数据量！您的第二个示例(介于1和5之间或id介于10000000和10000005之间)看起来不是该方法的一个很好的候选者。但是，它取决于行数，而不是id的数量。

关于和:您的示例是矛盾的(id在1和5之间，id在10000000和10000005之间)，查询将不会返回任何行。一些优化器能够“看到”这一点。

而不同列上的条件将通过连接索引来解决。

请查看我的网络书籍Use The Index, Luke!以了解更多详细信息。