2012-10-01 23 views
5

Tôi đã có một bảng lớn với một cái gì đó giống như 8 300 000 hàng (sẽ không được chỉnh sửa cũng không xóa bao giờ).Tăng tốc các chỉ mục của tôi trong MySQL - CRC hoặc MD5?

Cột đầu tiên của tôi trông giống như vậy P300-4312B_X16_S và mục nhập không phải là duy nhất vì vậy tôi sử dụng INDEX thông thường trên trường này.

Tuy nhiên, MySQL nhanh hơn bằng cách sử dụng trường nhị phân thay vì một varchar vì vậy tôi mã hóa INDEX của tôi trong MD5 bằng cách sử dụng BINARY(16) để lưu trữ dữ liệu.

Sáng nay, tôi bắt đầu sử dụng CRC32 lần đầu tiên và tôi thấy rằng CRC32 có thể được xuất dưới dạng chuỗi thập lục phân bằng 8 ký tự.

Câu hỏi của tôi: Nếu tôi sử dụng CRC32 thay vì MD5, nó sẽ nhanh hơn. Tuy nhiên, khi CRC32 được chạy qua, giả sử 2 000 000 giá trị duy nhất, kết quả sẽ là duy nhất hoặc có thể đôi khi tôi sẽ có hai lần cùng một chuỗi cho hai chuỗi differents? Tôi hỏi rằng vì kết quả chỉ dài 8 ký tự (32b) thay vì 32 (128b) như MD5.

Cảm ơn.

+0

hãy xem trang này: http://www.dslreports.com/forum/remark,13525942 – jcho360

+1

Tất nhiên bạn sẽ nhận được nhiều xung đột hơn với CRC32. Nó là một công cụ để kiểm tra tính toàn vẹn dữ liệu, không phải là hàm băm như md5. Hàm băm được thiết kế để tạo ra ít va chạm (cùng một kết quả cho đầu vào khác nhau) nhất có thể. CRC thì không. – dmitry

+0

'Tuy nhiên, MySQL là WAY nhanh hơn bằng cách sử dụng một trường nhị phân thay vì một varchar vì vậy tôi mã hóa INDEX của tôi trong MD5 bằng cách sử dụng BINARY (16) để lưu trữ dữ liệu.' Có vẻ như chỉ mục của bạn bị hỏng. Lập chỉ mục trên một 'VARCHAR' sẽ hoạt động tốt .. –

Trả lời

7

Số lần va chạm dự kiến ​​là số cặp trên số giá trị kiểm tra có thể có. Vì vậy, đối với 2.000.000 giá trị có (2000000 * 1999999)/2 cặp, tức là khoảng 2x10 . Đối với CRC 32 bit, số lần va chạm dự kiến ​​là trên 2 , là 466. Vì vậy, về cơ bản, bạn được bảo đảm có xung đột trong trường hợp đó.

Đối với giá trị kiểm tra MD5 128 bit, số lần va chạm dự kiến ​​là khoảng 6x10 -27. Đối với các giá trị nhỏ của số dự kiến, đó cũng là xác suất của một va chạm.

Nếu điều quan trọng là bạn phải có xác suất va chạm rất thấp, thì bạn cần phải chọn một thứ khác ngoài CRC-32.

Mặc dù vậy, bạn không cần chi phí của MD5, nơi cường độ mã hóa của nó không quan trọng đối với ứng dụng của bạn. Bạn không thực sự quan tâm nếu ai đó độc hại có thể tìm cách để chế tạo một mục có cùng giá trị kiểm tra như một mục nhập khác. Vì vậy, bạn có thể sử dụng một băm không mã hóa 64 bit được thiết kế cho mục đích đó, sẽ chạy nhanh hơn nhiều và sẽ cung cấp xác suất 10 -7 của một vụ va chạm trong trường hợp của bạn là 2.000.000 giá trị. Hoặc bạn có thể sử dụng mã băm không mã hóa 128 bit và nhận được xác suất tương tự như đối với MD5, nhưng nhanh hơn nhiều. Hãy xem CityHash family các thuật toán băm.

Tuy nhiên, lưu ý rằng trong mọi trường hợp, xác suất xảy ra va chạm không bằng 0. Bạn nên xem xét hậu quả của một vụ va chạm với mã của bạn.

+0

Tôi thích câu trả lời của bạn bởi vì bây giờ tôi hiểu được logic đằng sau "băm". Tôi không quan tâm nếu khách truy cập tìm thấy băm được mã hóa, nó chỉ để xác định một chuyến đi xe buýt. Nếu anh ta tìm thấy nó sau đó anh ta sẽ tìm thấy một chuyến đi xe buýt ngẫu nhiên ... không có vấn đề lớn. Tôi sẽ xem xét gia đình CityHash. Cảm ơn. –

Các vấn đề liên quan