在類似數據庫的數據結構中高效實現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通常表示您只需要兩個條件......