Chỉ mục băm SQL Server

Question

Khi sử dụng loại cột CHECKSUM để tạo chỉ mục băm giả tạo, tra cứu có thực sự là O (1) hay vẫn là O (lg n) giống như chỉ mục được nhóm? Tôi có một bảng mà từ đó tôi sẽ chọn dựa trên cột ID của nó và tôi cần tra cứu càng nhanh càng tốt, do đó, chỉ mục nhóm có thể là tùy chọn nhanh nhất có thể? Tôi đang tìm cái gì đó sẽ cung cấp O (1) hiệu suất.

Answer 1

Ok, 2 điểm.
Hàm CHECKSUM SQL không tạo ra giá trị băm. Nó thực sự tính toán giá trị CRC. Nó không phải là một ứng viên rất tốt để kiểm tra cơ sở băm bởi vì sẽ có một số lượng lớn các vụ va chạm tương đối. Bạn nên kiểm tra hàm hash_bytes nếu bạn muốn hàm băm.
Thứ hai, bạn không thực sự tạo chỉ mục băm. Bạn đang tạo một cây b bình thường trên một giá trị băm nên thời gian tra cứu sẽ giống hệt với bất kỳ chỉ mục b-tree nào khác trên một kiểu dữ liệu có kích thước tương tự.
Có khả năng bạn có thể đạt được hiệu suất nhỏ bằng cách sử dụng CRC hoặc giá trị băm dài để cho phép so sánh số lượng byte nhỏ hơn, nhưng so sánh chuỗi chỉ kiểm tra nhiều byte khi cần, điều này giống như xa như ký tự đầu tiên không khớp, và nếu bạn khớp với giá trị băm, thì bạn cần phải kiểm tra lại giá trị thực. Vì vậy, trừ khi bạn có rất nhiều chuỗi rất giống nhau, bạn có thể sẽ kết thúc so sánh các byte THÊM bằng cách sử dụng hàm băm (hoặc CRC).

Tóm lại, tôi không nghĩ đây là một kế hoạch hợp lý, nhưng như với tất cả các tối ưu hóa bạn nên kiểm tra nó trong trường hợp cụ thể của bạn và sau đó quyết định. Tôi sẽ quan tâm để xem kết quả của bạn nếu bạn quan tâm để đăng chúng. Và tôi không tin rằng có bất kỳ cách nào nhanh hơn để định vị một hàng trong máy chủ SQL hơn là bằng cách sử dụng một chỉ số nhóm.

Trong trường hợp bạn quan tâm, Ingres (theo CA) có thể tạo chỉ mục băm sau đó sẽ đạt được O (1). có thể có RDBM khác ra khỏi đó cũng hỗ trợ các chỉ số băm thực sự.

Answer 2

Không có lợi thế nào khi tìm kiếm CHECKSUM được lập chỉ mục trên chỉ mục nhóm trên trường ID nếu trường ID là int vì cả hai sẽ thực hiện tìm kiếm chỉ mục nhóm. Ngoài ra, cột CHECKSUM của cột int luôn trả về cùng giá trị với cột (tức là CHECKSUM (535) = 535). Tuy nhiên, một tra cứu CHECKSUM thường sẽ hoạt động tốt hơn nếu ID là một cột ký tự dài.

Answer 3

Bạn có thể thử thiết lập mọi thứ để sử dụng phép nối băm, bạn có thể xem kế hoạch thực hiện để xác minh một phép nối băm thực sự được sử dụng. Khi tham gia băm được sử dụng, SQL Server sẽ vẫn xây dựng bảng băm đầu tiên như một phần của việc thực hiện truy vấn riêng lẻ. Tôi tin rằng các chỉ mục không bao giờ được lưu trữ dưới dạng băm, chỉ là cây cối.

Nói chung tôi sẽ không tạo cột băm nhân tạo trừ khi bạn đang thực hiện khớp chính xác với các chuỗi có khả năng lớn hoặc các đốm màu nhị phân (như pipTheGeek đề cập đến). Tôi chỉ muốn thêm rằng đôi khi điều này là cần thiết vì các chuỗi có thể quá lớn để vừa với một khóa chỉ mục. Có một giới hạn về kích thước của các phím chỉ mục của tôi nghĩ 2k cho SQL Server.

Tất nhiên, khi tham gia, bạn cần bao gồm cột băm và cột nguồn để giải quyết bất kỳ sự mơ hồ nào phát sinh từ băm.

Answer 4

Tôi không nghĩ rằng máy chủ SQL nguyên bản có chỉ mục dựa trên bảng băm. Các BOL documentation đang nói về việc xây dựng một tiêu chuẩn (cây) chỉ số trên một giá trị tính toán. Đây không phải là điều tương tự như một Linear Hash Table, mà là một cấu trúc chỉ mục có sẵn trên một số nền tảng DBMS, nhưng không phải là SQL Server (AFAIK).

Bạn có thể nhận được một số lợi ích từ việc sử dụng kỹ thuật được mô tả trong this blog post để băm các giá trị chuỗi lớn như URL để tra cứu nhanh hơn. Tuy nhiên, chỉ số cơ bản vẫn là một cấu trúc cây và là O (Log N).