Bertentangan dengan poster sebelumnya, saya tidak berpikir Anda bisa mendapatkan kompleksitas O(log n) dengan menggunakan pengindeksan naif. Mari kita pertimbangkan mongodb misalnya. Anda dapat menentukan dua indeks (untuk properti awal dan akhir dari rentang), tetapi mongodb hanya akan menggunakan satu untuk menyelesaikan kueri yang diberikan. Jadi itu tidak akan berhasil. Sekarang jika Anda menggunakan indeks gabungan tunggal yang melibatkan properti awal dan akhir dari rentang, kompleksitasnya akan menjadi logaritmik untuk menemukan rentang pertama yang diperiksa, tetapi kemudian akan menjadi linier untuk menemukan rentang terakhir yang cocok dengan kueri. Kompleksitas kasus terburuk adalah O(n), dan Anda memilikinya ketika semua rentang yang disimpan tumpang tindih dengan input Anda.
Di samping catatan, menggunakan Redis diurutkan set Anda dapat meniru indeks yang diurutkan (dengan kompleksitas O(log n)) jika Anda tahu apa yang Anda lakukan. Redis sedikit lebih dari sekadar penyimpanan nilai kunci sederhana. Kumpulan redis yang diurutkan diimplementasikan menggunakan daftar lewati, dan skor serta nilai digunakan untuk membandingkan item.
Untuk mengatasi masalah semacam ini, diperlukan struktur pengindeksan khusus. Anda mungkin ingin melihat:
http://en.wikipedia.org/wiki/Segment_treeatauhttp://en.wikipedia.org/wiki/Interval_tree
Jika masalahnya adalah kecepatan di atas ruang, maka mungkin menarik untuk meratakan indeks. Misalnya, mari kita pertimbangkan rentang berikut (hanya menggunakan bilangan bulat untuk menyederhanakan diskusi):
A 2-8
B 4-6
C 2-9
D 7-10
Struktur yang jarang mengindeks segmen yang tidak tumpang tindih dapat dibangun.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Setiap entri berisi batas bawah segmen yang tidak tumpang tindih sebagai kunci, dan daftar atau kumpulan rentang yang cocok sebagai nilai. Entri harus diindeks menggunakan wadah yang diurutkan (pohon, daftar lewati, btree, dll ...)
Untuk menemukan rentang yang cocok dengan 5, kami mencari entri pertama yang lebih rendah atau sama dengan 5 (dalam contoh ini akan menjadi 4) dan daftar rentang disediakan ( [A C B] )
Dengan struktur data ini, kompleksitas kueri benar-benar O(log n). Namun tidak sepele (dan mahal) untuk membangun dan memeliharanya. Ini dapat diimplementasikan dengan mongodb dan Redis.
Berikut adalah contoh dengan 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"
