Tại sao Lucene sử dụng mảng thay vì các bảng băm cho chỉ mục đảo ngược của nó?

Question

Tôi đã xem Adrien Grand's talk on Lucene's index architecture và một điểm mà anh ta tạo ra là Lucene sử dụng các mảng được sắp xếp để biểu diễn phần từ điển của các chỉ số đảo ngược của nó. Lý do đằng sau việc sử dụng các mảng được sắp xếp thay vì các bảng băm (cấu trúc dữ liệu chỉ mục "cổ điển" ngược) là gì?

Bảng băm cung cấp O (1) chèn và truy cập, mà với tôi có vẻ như nó sẽ giúp rất nhiều với xử lý nhanh các truy vấn và hợp nhất các phân đoạn chỉ mục. Mặt khác, các mảng được sắp xếp chỉ có thể cung cấp truy cập O (logN) và chèn (O), mặc dù sáp nhập 2 mảng được sắp xếp có cùng độ phức tạp như hợp nhất 2 bảng băm. Một trong những nhược điểm duy nhất cho bảng băm mà tôi có thể nghĩ là dấu chân bộ nhớ lớn hơn (điều này thực sự có thể là vấn đề) và ít thân thiện với bộ nhớ cache hơn (mặc dù các hoạt động như truy vấn mảng được sắp xếp yêu cầu tìm kiếm nhị phân, cũng giống như bộ nhớ cache không thân thiện) .

Vậy có chuyện gì? Các nhà phát triển Lucene phải có một lý do rất tốt để sử dụng mảng. Có liên quan gì đến khả năng mở rộng không? Tốc độ đọc đĩa? Cái gì khác hoàn toàn?

Answer 1

Vâng, tôi sẽ suy đoán tại đây (có thể có thể là nhận xét - nhưng sẽ quá dài).

1. HashMap là nói chung một cấu trúc nhanh chóng nhìn lên có thời gian tìm kiếm O(1) - có nghĩa là nó không đổi. Nhưng đó là trường hợp trung bình ; kể từ khi (ít nhất là bằng Java), HashMap sử dụng TreeNodes - tìm kiếm là O(logn) bên trong nhóm đó. Ngay cả khi chúng tôi đối xử với sự phức tạp tìm kiếm của họ là O(1), điều đó không có nghĩa là nó là cùng một thời điểm. Nó chỉ có nghĩa là nó là hằng số cho mỗi cấu trúc dữ liệu riêng biệt.

2. Bộ nhớ Thật vậy - Tôi sẽ đưa ra một ví dụ here. Trong lưu trữ ngắn 15_000_000 mục sẽ yêu cầu một ít hơn 1GB bộ nhớ RAM; các mảng được sắp xếp có lẽ nhỏ gọn hơn nhiều, đặc biệt là vì chúng có thể giữ nguyên thủy, thay vì các đối tượng.

3. mục phải đặt trong một HashMap (thường) yêu cầu tất cả những chìa khóa để tái băm mà có thể là một hiệu suất đáng kể hit, vì tất cả họ đều phải di chuyển đến địa điểm khác nhau có khả năng.

4. Có thể là một điểm phụ ở đây - tìm kiếm trong phạm vi, có thể yêu cầu một số TreeMap có thể, trong đó các mảng phù hợp hơn nhiều ở đây. Tôi đang suy nghĩ về phân vùng một chỉ số (có thể là họ làm điều đó trong nội bộ).

5. Tôi có ý tưởng giống như bạn - mảng thường là bộ nhớ tiếp giáp, có thể dễ dàng hơn khi được tìm nạp trước bởi CPU.

6. Và điểm cuối cùng: đặt tôi vào giày của họ, tôi sẽ bắt đầu với số HashMap trước tiên ... Tôi chắc chắn có những lý do thuyết phục cho quyết định của họ. Tôi tự hỏi liệu họ có thử nghiệm thực tế chứng minh sự lựa chọn này không.