前のポスターとは異なり、ナイーブなインデックスを使用してもO（log n）の複雑さを得ることができないと思います。たとえば、mongodbについて考えてみましょう。 2つのインデックス（範囲の開始プロパティと終了プロパティ）を定義できますが、mongodbは特定のクエリを解決するために1つだけを使用します。したがって、機能しません。ここで、範囲の開始プロパティと終了プロパティの両方を含む単一の複合インデックスを使用する場合、チェックする最初の範囲を見つけるための複雑さは対数になりますが、クエリに一致する最後の範囲を見つけるために線形になります。最悪の場合の複雑さはO（n）であり、保存されているすべての範囲が入力と重なる場合に発生します。
ちなみに、Redisの並べ替えられたセットを使用すると、自分が何をしているのかがわかっている場合は、並べ替えられたインデックス（O（log n）の複雑さ）をエミュレートできます。 Redisは、単純なKey-Valueストアを少し超えています。Redisで並べ替えられたセットはスキップリストを使用して実装され、スコアと値の両方がアイテムの比較に使用されます。
この種の問題を解決するには、専用のインデックス構造が必要です。ご覧になることをお勧めします：
http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree
懸念が空間上の速度である場合は、インデックスを平坦化することが興味深い場合があります。たとえば、次の範囲を考えてみましょう（説明を簡略化するために整数のみを使用）：
A 2-8
B 4-6
C 2-9
D 7-10
重複しないセグメントにインデックスを付けるスパース構造を構築できます。
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
各エントリには、重複しないセグメントの下限がキーとして含まれ、一致する範囲のリストまたはセットが値として含まれます。エントリは、ソートされたコンテナ（ツリー、スキップリスト、btreeなど）を使用してインデックス付けする必要があります
5に一致する範囲を見つけるために、5以下（この例では4）の最初のエントリを探し、範囲のリストを提供します（[A C B]）
このデータ構造では、クエリの複雑さは実際にはO（log n）です。ただし、それを構築して維持することは簡単ではありません（そして費用がかかります）。 mongodbとRedisの両方で実装できます。
これがRedisの例です：
> rpush range:2 2-8 2-9
(integer) 2
> rpush range:4 2-8 2-9 4-6
(integer) 3
> rpush range:7 2-8 2-9 7-10
(integer) 3
> rpush range:9 2-9 7-10
(integer) 2
> rpush range:10 7-10
(integer) 1
> zadd range_index 0 range:0 2 range:2 4 range:4 7 range:7 9 range:9 10 range:10
(integer) 6
> zrevrangebyscore range_index 5 0 LIMIT 0 1
1) "range:4"
> lrange range:4 0 -1
1) "2-8"
2) "2-9"
3) "4-6"