B-Tree vs Hash Bảng

Question

Trong MySQL, một loại chỉ mục là một cây b, và truy cập một phần tử trong một cây b là trong thời gian phân bổ logarit O(log(n)).

Mặt khác, việc truy cập phần tử trong bảng băm là O(1).

Tại sao bảng băm không được sử dụng thay cho cây b để truy cập dữ liệu bên trong cơ sở dữ liệu?

Answer 1

Bạn chỉ có thể truy cập các yếu tố bằng khóa chính của chúng trong một thẻ bắt đầu bằng #. Đây là nhanh hơn so với một thuật toán cây (O(1) thay vì log(n)), nhưng bạn không thể chọn dãy (tất cả mọi thứ ở giữa x và y). Thuật toán cây hỗ trợ điều này trong Log(n) trong trường hợp chỉ mục băm có thể dẫn đến quét toàn bộ bảng O(n). Ngoài ra chi phí liên tục của các chỉ mục băm thường lớn hơn (không có yếu tố trong ký hiệu theta, nhưng nó vẫn tồn tại). Ngoài ra thuật toán cây thường dễ bảo trì hơn, phát triển với dữ liệu, tỷ lệ, v.v.

Chỉ mục băm làm việc với kích thước băm được xác định trước, vì vậy bạn kết thúc với một số "nhóm" nơi đối tượng được lưu trữ. được lặp lại để thực sự tìm thấy đúng bên trong phân vùng này.

Vì vậy, nếu bạn có kích thước nhỏ, bạn có rất nhiều chi phí cho các yếu tố nhỏ, kích thước lớn dẫn đến quét thêm.

Thuật toán bảng băm diễn ra thường là tỷ lệ, nhưng tỷ lệ có thể không hiệu quả.

Thực sự có các thuật toán băm có thể mở rộng. Đừng hỏi tôi làm thế nào điều đó hoạt động - đó là một điều vô cùng với tôi. AFAIK chúng phát triển từ nhân rộng có thể mở rộng, nơi việc băm lại không dễ dàng.

của nó được gọi là RUSH - R eplication U nder S calable H tro, và do đó những thuật toán được gọi là thuật toán RUSH.

Tuy nhiên, có thể có một điểm mà chỉ mục của bạn vượt quá kích thước có thể chấp nhận được so với kích thước băm và toàn bộ chỉ mục của bạn cần được xây dựng lại. Thông thường đây không phải là một vấn đề, nhưng đối với cơ sở dữ liệu khổng lồ lớn, điều này có thể mất vài ngày.

Việc trao đổi thuật toán cây nhỏ và chúng phù hợp cho hầu hết mọi trường hợp sử dụng và do đó là mặc định.

Tuy nhiên nếu bạn có trường hợp sử dụng rất chính xác và bạn biết chính xác điều gì và chỉ những gì sẽ cần, bạn có thể tận dụng các chỉ mục băm.

Answer 2

Độ phức tạp về thời gian của hashtables chỉ liên tục cho các thẻ bắt đầu có kích thước đủ (có đủ nhóm để giữ dữ liệu). Kích thước của một bảng cơ sở dữ liệu không được biết trước nên bảng phải được phục hồi ngay bây giờ và sau đó để có được hiệu suất tối ưu từ một hashtable. Việc phục hồi cũng đắt tiền.

Answer 3

Tôi nghĩ rằng Hashmaps cũng không mở rộng quy mô và có thể tốn kém khi toàn bộ bản đồ cần được phục hồi.

Answer 4

Thực ra, có vẻ như MySQL sử dụng cả hai loại chỉ mục hoặc bảng băm hoặc cây b theo sau link.

Sự khác biệt giữa việc sử dụng một b-tree và một bảng băm là cựu phép bạn sử dụng so sánh cột trong các biểu thức mà sử dụng =,>,> =, <, < =, hoặc GIỮA nhà khai thác, trong khi cái sau chỉ được sử dụng chỉ để so sánh bình đẳng sử dụng toán tử = hoặc < =>.