Trái ngược với người đăng trước đó, tôi không nghĩ rằng bạn có thể có được độ phức tạp O (log n) bằng cách sử dụng lập chỉ mục ngây thơ. Hãy xem xét mongodb chẳng hạn. Bạn có thể xác định hai chỉ mục (cho thuộc tính đầu và cuối của phạm vi), nhưng mongodb sẽ chỉ sử dụng một chỉ mục để giải quyết một truy vấn nhất định. Vì vậy, nó sẽ không hoạt động. Bây giờ nếu bạn sử dụng một chỉ số ghép đơn liên quan đến cả thuộc tính bắt đầu và kết thúc của phạm vi, độ phức tạp sẽ là logarit để tìm phạm vi đầu tiên cần kiểm tra, nhưng sau đó nó sẽ tuyến tính để tìm phạm vi cuối cùng phù hợp với truy vấn. Độ phức tạp trong trường hợp xấu nhất là O (n) và bạn có nó khi tất cả các phạm vi được lưu trữ chồng lên nhau đầu vào của bạn.
Một lưu ý nhỏ là, sử dụng tập hợp được sắp xếp của Redis, bạn có thể mô phỏng một chỉ mục được sắp xếp (với độ phức tạp O (log n)) nếu bạn biết mình làm gì. Redis không chỉ là một kho lưu trữ khóa-giá trị đơn giản. Các tập hợp được sắp xếp của redis được triển khai bằng cách sử dụng danh sách bỏ qua và cả điểm số và giá trị đều được sử dụng để so sánh các mục.
Để giải quyết loại vấn đề này, cần có một cấu trúc lập chỉ mục chuyên dụng. Bạn có thể muốn xem:
http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree
Nếu mối quan tâm là tốc độ trên không gian, thì việc san bằng chỉ mục có thể thú vị. Ví dụ, chúng ta hãy xem xét các phạm vi sau (chỉ sử dụng số nguyên để đơn giản hóa cuộc thảo luận):
A 2-8
B 4-6
C 2-9
D 7-10
Có thể tạo cấu trúc thưa thớt lập chỉ mục các phân đoạn không chồng chéo.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Mỗi mục nhập chứa giới hạn dưới của một phân đoạn không chồng chéo làm khóa và danh sách hoặc tập hợp các phạm vi phù hợp dưới dạng một giá trị. Các mục nhập phải được lập chỉ mục bằng cách sử dụng một vùng chứa được sắp xếp (cây, danh sách bỏ qua, btree, v.v.)
Để tìm các phạm vi phù hợp với 5, chúng tôi tìm mục nhập đầu tiên thấp hơn hoặc bằng 5 (trong ví dụ này sẽ là 4) và danh sách các phạm vi được cung cấp ([A C B])
Với cấu trúc dữ liệu này, độ phức tạp của các truy vấn thực sự là O (log n). Tuy nhiên, nó không phải là tầm thường (và tốn kém) để xây dựng và duy trì nó. Nó có thể được triển khai với cả mongodb và Redis.
Đây là một ví dụ với 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"
