在类似数据库的数据结构中高效实现AND

Question

我可以想象如何在某些列上实现简单的数据库和索引 - 只需将列值保持在某种平衡树中即可。

这个问题是关于什么，AND查询将如何有效地实现？你将如何实现像

SELECT * FROM points WHERE x > 0 and x < 4 and y > 10 and y < 14 

请注意，我不是数据库专门询问，而是它的数据结构将是最适合这在实践中，二维查询。我记得一次约Range Trees - 这是这个问题的真实世界的解决方案？

Answer 1

你可以很有效地做到这一点与常规搜索树...

，你也可以做到这一点在O（N），扫描整个数据，而这正是我想大多数的DB做最时间。特别是考虑到指数的成本。

任何方式，这是最常见，最简单的一种指标，在大多数的DB支持：http://en.wikipedia.org/wiki/B-tree，所以如果你正在寻找一个范围在指数的相对容易优化...

顺便说考虑此外，您希望数据库了解您正在寻找范围并据此进行优化，因为AND通常表示您只需要两个条件......