[解決済み] なぜMongoDBではインデックスの方向が重要なのか？

疑問点

引用元 ドキュメント :

インデックスを作成する際、キーに関連付けられた数値はインデックスの方向を指定します。 したがって、常に1（昇順）または-1（降順）でなければなりません。 (降順) でなければなりません。方向は、単一のキーインデックスやランダムアクセス検索では重要ではありません。 しかし、複合インデックスでソートや範囲検索を行う場合は重要です。 レンジクエリを行う場合には重要です。

しかし、複合インデックスにおいてインデックスの方向が重要である理由は見当たりません。どなたか詳しい説明 (または例) をしていただけませんか？

どのように解決するのですか？

MongoDBは複合キーを何らかの方法で連結し、BTreeのキーとして使用します。

単体を探す場合 - ツリー内のノードの順番は関係ありません。

ノードの範囲を返す場合 - 互いに近い要素は、ツリーの同じ枝を下ることになります。範囲内のノードが近ければ近いほど、より早く取得することができます。

単一フィールドインデックスで - 順序は重要ではありません。もし昇順で近ければ、降順でも近づけるでしょう。

複合キーがある場合 - 順序が重要になり始める。

例えば、キーがAの昇順、Bの昇順の場合、インデックスは次のようになります。

行 A B
1 1 1
2 2 6
3 2 7 
4 3 4
5 3 5
6 3 6
7 5 1

Aの昇順Bの降順のクエリは、行を返すためにインデックスの周りを順番通りに飛ぶ必要があり、より遅くなります。例えば、このクエリが返す行は 1, 3, 2, 6, 5, 4, 7

インデックスと同じ順序で範囲指定されたクエリは、単に正しい順序で行を順次返します。

BTreeでレコードを見つけるにはO(Log(n))の時間がかかります。レコードの範囲を順番に見つけることは、OLog(n) + k (kは返すべきレコードの数)だけです。

レコードが順番通りでない場合、コストはOLog(n) * kと同じくらいになる可能性があります。