什麼樣的數據結構用於複合索引？

Question

來自MongoDB的文檔：MongoDB索引使用B樹數據結構。

但是，它是否也適用於複合索引？在肯定的情況下，它是如何實際執行的？

PD：我想象的唯一方式就是將每個節點都沒有單個值，但是存儲的索引值存儲在一個數組中（例如，如果兩個二叉樹（或更多，每個索引一個）已合併）。

Answer 1

對於實際的實現，我不能說100％的確定性，但我確實認爲複合索引也實現爲B樹，正如您所描述的那樣，具有值序列的節點（尊重索引鍵訂單），非常重要的是對關鍵值使用字典順序。儘管如此，爲了節省一些空間，我還會考慮一個僅使用與樹頂部第一個鍵相關的值的B樹，然後第二個鍵的值會進一步變化向下，...以及靠近樹葉的最後一個鍵的值。這不是別的，而是使節點的邊界與各個鍵重合的優化。

實現複合索引這樣（有或沒有上述優化）的優點是，如果你有幾個關鍵的指標，比方說A然後B然後是C，那麼你就得到一個指數A單獨免費，並且免費索引A然後B：事實上，由於詞典順序，鍵序列的任何前綴的所有值總是在這樣的B樹中組合在一起。

既然MongoDB documents就是這種情況，那麼我在使用MongoDB的時候就這樣想到了複合索引的實現。

此外，該文檔還指定在混合索引上禁止散列索引字段。這是更多的線索，因爲B樹實現了範圍指數。另外，我希望MongoDB的散列索引是用散列表而不是B樹來實現的，因爲僅使用B-樹來進行點查詢的效率會比較低（對數查找與O（1） ）