Chỉ mục băm là một phần không thể thiếu của cơ sở dữ liệu. Nếu bạn đã từng sử dụng cơ sở dữ liệu, rất có thể bạn đã thấy chúng hoạt động mà không hề nhận ra.
Chỉ mục băm khác về công việc với các loại chỉ mục khác vì chúng lưu trữ các giá trị chứ không phải là con trỏ tới các bản ghi nằm trên đĩa. Điều này đảm bảo việc tìm kiếm và chèn vào chỉ mục nhanh hơn. Đó là lý do tại sao chỉ mục băm thường được sử dụng làm khóa chính hoặc số nhận dạng duy nhất.
Hiểu về Chỉ số băm
Chỉ mục băm là một loại chỉ mục được sử dụng phổ biến nhất trong quản lý dữ liệu. Nó thường được tạo trên một cột chứa các giá trị duy nhất, chẳng hạn như khóa chính hoặc địa chỉ email. Lợi ích chính của việc sử dụng chỉ mục băm là hiệu suất nhanh của chúng.
Khái niệm đằng sau các chỉ mục này có thể phức tạp để hiểu đối với những người chưa bao giờ nghe nói về chúng trước đây. Tuy nhiên, việc hiểu các chỉ mục băm là rất quan trọng nếu bạn cần hiểu cơ sở dữ liệu hoạt động như thế nào. Nó cần thiết để giải quyết các vấn đề chung liên quan đến cơ sở dữ liệu và tốc độ của chúng.
Tin tốt là với một chút kiên nhẫn và tắt điện thoại di động, chắc chắn bạn có thể nắm vững các chỉ mục băm! Vì vậy, chúng ta hãy xem xét kỹ hơn.
Nhanh chóng và Dễ dàng
Chỉ mục băm là một cấu trúc dữ liệu có thể được sử dụng để tăng tốc các truy vấn cơ sở dữ liệu. Nó hoạt động bằng cách chuyển đổi các bản ghi đầu vào thành một mảng các nhóm. Mỗi nhóm có cùng số lượng bản ghi với tất cả các nhóm khác trong bảng. Do đó, bất kể bạn có bao nhiêu giá trị khác nhau cho một cột cụ thể, mọi hàng sẽ luôn ánh xạ vào một nhóm.
Chỉ mục băm cho phép tra cứu nhanh dữ liệu được lưu trữ trong bảng. Chúng hoạt động bằng cách tạo một khóa chỉ mục từ giá trị và sau đó định vị nó dựa trên hàm băm kết quả. Nó hữu ích khi có nhiều dữ liệu đầu vào với các giá trị tương tự hoặc trùng lặp, vì nó chỉ cần so sánh các khóa thay vì xem qua tất cả các bản ghi.
Điều này không nhanh chóng cũng không dễ dàng? Để hiểu cách hoạt động của chỉ mục băm và tại sao chúng lại mạnh mẽ như vậy, bạn cần hiểu ý nghĩa của việc băm.
Băm đang lấy một phần thông tin (một chuỗi) và biến nó thành một địa chỉ hoặc con trỏ để truy cập nhanh sau này.
Ý tưởng với băm là dữ liệu được gán một số nhỏ. Khi tra cứu dữ liệu, bạn không cần phải sàng lọc hàng loạt. Thay vào đó, chỉ cần tra cứu một số đó. Ví dụ đơn giản nhất là Ctrl + F-ing từ bạn đang tìm kiếm trong văn bản thay vì tự đọc hàng chục trang.
Chỉ mục băm dùng để làm gì?
Chỉ mục băm là một cách để tăng tốc quá trình tìm kiếm. Với các chỉ mục truyền thống, bạn phải quét qua từng hàng để đảm bảo rằng truy vấn của bạn thành công. Nhưng với chỉ mục băm, điều này không đúng!
Mỗi khóa của chỉ mục chỉ chứa một hàng của dữ liệu bảng và sử dụng thuật toán lập chỉ mục được gọi là băm chỉ định cho chúng một vị trí duy nhất trong bộ nhớ, loại bỏ tất cả các khóa khác có giá trị trùng lặp trước khi tìm thấy những gì nó đang tìm kiếm.
Chỉ mục băm là một trong nhiều cách để tổ chức dữ liệu trong cơ sở dữ liệu. Chúng hoạt động bằng cách lấy dữ liệu đầu vào và sử dụng nó làm khóa để lưu trữ trên đĩa. Những khóa hoặc giá trị băm này , có thể là bất kỳ thứ gì từ độ dài chuỗi đến ký tự trong đầu vào.
Chỉ mục băm được sử dụng phổ biến nhất khi truy vấn đầu vào cụ thể với các thuộc tính cụ thể. Ví dụ, nó có thể tìm tất cả các chữ cái A cao hơn 10 cm. Bạn có thể làm điều đó nhanh chóng bằng cách tạo một hàm chỉ mục băm.
Các chỉ mục băm là một phần của hệ thống cơ sở dữ liệu PostgreSQL. Hệ thống này được phát triển để tăng tốc độ và hiệu suất. Chỉ mục băm có thể được sử dụng cùng với các loại chỉ mục khác, chẳng hạn như B-tree hoặc GiST.
Chỉ mục băm lưu trữ các khóa bằng cách chia chúng thành các phần nhỏ hơn được gọi là nhóm, trong đó mỗi nhóm được cấp một số ID số nguyên để truy xuất nó nhanh chóng khi tìm kiếm vị trí của khóa trong bảng băm. Các nhóm được lưu trữ tuần tự trên đĩa để dữ liệu chứa chúng có thể được truy cập nhanh chóng.
Có thể tìm thấy nhiều giải thích kỹ thuật hơn trên trang này (nhấp chuột phải và chọn “Dịch sang tiếng Anh”).
Ưu điểm
Ưu điểm chính của việc sử dụng chỉ mục băm là chúng cho phép truy cập nhanh khi truy xuất bản ghi theo giá trị khóa. Nó thường hữu ích cho các truy vấn có điều kiện bình đẳng. Ngoài ra, việc sử dụng điểm chuẩn băm sẽ không yêu cầu nhiều dung lượng lưu trữ. Vì vậy, nó là một công cụ hữu hiệu, nhưng không phải không có nhược điểm.
Nhược điểm
Chỉ mục băm là một cấu trúc lập chỉ mục tương đối mới với tiềm năng cung cấp các lợi ích hiệu suất đáng kể. Bạn có thể coi chúng như một phần mở rộng của cây tìm kiếm nhị phân (BST).
Chỉ mục băm hoạt động bằng cách lưu trữ dữ liệu trong các nhóm dựa trên các giá trị băm của chúng, điều này cho phép truy xuất dữ liệu nhanh chóng và hiệu quả. Chúng được đảm bảo theo thứ tự.
Tuy nhiên, không thể lưu trữ các khóa trùng lặp trong một thùng. Do đó, sẽ luôn có một số chi phí. Nhưng cho đến nay, ưu điểm của việc sử dụng chỉ mục băm nhiều hơn nhược điểm.
Làm thế nào để tất cả hoạt động chuyên sâu hơn một chút?
Hãy xem bản trình diễn aviasales cơ sở dữ liệu để hiểu sâu hơn về cách hoạt động của chỉ mục băm.
demo=# create index on flights using hash(flight_no);
WARNING: hash indexes are not WAL-logged and their use is discouraged
CREATE INDEX
demo=# explain (costs off) select * from flights where flight_no = 'PG0001';
QUERY PLAN
----------------------------------------------------
Bitmap Heap Scan on flights
Recheck Cond: (flight_no = 'PG0001'::bpchar)
-> Bitmap Index Scan on flights_flight_no_idx
Index Cond: (flight_no = 'PG0001'::bpchar)
(4 rows)
Tại đây, bạn có thể thấy cách chúng tôi đang triển khai chỉ mục băm bằng cách tổng hợp dữ liệu thành các tập hợp.
Đây là một ví dụ dễ hiểu, nhưng lưu ý rằng các hạn chế đi kèm với cơ sở hạ tầng mã ít hơn. Có thể thiếu quyền truy cập nhật ký WAL hoặc không thể khôi phục các chỉ mục (chỉ số?) Sau sự cố. Bên cạnh đó, các chỉ mục có thể không tham gia vào quá trình nhân rộng - đó là do PostgreSQL đã lỗi thời. Tuy nhiên, giống như với Python, bạn thường nhận được các cảnh báo cho phép bạn ngăn chặn sai lầm.
Bạn có thể xem xét sâu hơn bên trong các chỉ mục này nếu bạn đủ quan tâm. Vì lý do đó, chúng tôi đang tạo kiểm tra trang phiên bản tiện ích mở rộng.
demo=# create extension pageinspect;
CREATE EXTENSION
demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',0));
hash_page_type
----------------
metapage
(1 row)
demo=# select ntuples, maxbucket from hash_metapage_info(get_raw_page('flights_flight_no_idx',0));
ntuples | maxbucket
---------+-----------
33121 | 127
(1 row)
demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',1));
hash_page_type
----------------
bucket
(1 row)
demo=# select live_items, dead_items from hash_page_stats(get_raw_page('flights_flight_no_idx',1));
live_items | dead_items
------------+------------
407 | 0
(1 row)
Nếu bạn muốn kiểm tra toàn bộ mã, hãy bắt đầu với README.
Tóm tắt
Chỉ mục băm là một cấu trúc dữ liệu giúp tăng tốc quá trình tìm kiếm thông tin trong cơ sở dữ liệu lớn. Chúng hoạt động bằng cách chia nhỏ dữ liệu thành các phần nhỏ hơn và sau đó sắp xếp chúng. Do đó, khi bạn tìm kiếm một thứ gì đó, bạn có thể tìm thấy nó nhanh hơn nhiều.
Nếu bạn muốn tra cứu nhiều thứ hơn, có các tài nguyên dành cho DYOR. Ngoài ra, hãy theo dõi các bài viết mới của chúng tôi, những bài viết này sẽ ra mắt nhanh hơn bạn có thể Ctrl + F từ “băm” trên trang này. Hy vọng điều này sẽ hữu ích!
