Các Phương pháp Lập chỉ mục và Truy cập

Chỉ mục và các phương pháp truy cập là các cấu trúc dữ liệu phụ trợ — chủ yếu là cây B+-tree và chỉ mục băm — cho phép cơ sở dữ liệu định vị các bộ dữ liệu phù hợp mà không cần quét toàn bộ bảng, cung cấp các đường dẫn truy cập nhanh mà trình tối ưu hóa dựa vào.

Definition

Chỉ mục là một cấu trúc dữ liệu phụ trợ trên một hoặc nhiều thuộc tính của một quan hệ, ánh xạ các giá trị khóa đến vị trí của các bộ dữ liệu phù hợp, cho phép truy xuất trong thời gian dưới tuyến tính so với kích thước bảng; phương pháp truy cập là cơ chế mà một truy vấn sử dụng để đọc dữ liệu, chẳng hạn như quét toàn bộ hoặc quét chỉ mục.

Scope

Chủ đề này bao gồm các cấu trúc và khái niệm đằng sau các đường dẫn truy cập dữ liệu: sự khác biệt giữa chỉ mục phân cụm và không phân cụm, chỉ mục chính và phụ; cây B+-tree là chỉ mục có thứ tự hiệu quả hỗ trợ tìm kiếm bằng và tìm kiếm theo phạm vi; các chỉ mục dựa trên băm để tìm kiếm bằng; và vai trò của chỉ mục trong việc chọn lọc, kết nối và tránh sắp xếp. Nó đề cập đến cách lựa chọn chỉ mục ảnh hưởng đến chi phí truy vấn và chi phí cập nhật. Nó không bao gồm việc lựa chọn kế hoạch tổng thể của trình tối ưu hóa dựa trên chi phí, đây là một chủ đề riêng biệt.

Core questions

• Làm thế nào một cây B+-tree hỗ trợ hiệu quả cả truy vấn bằng và truy vấn theo phạm vi?
• Sự khác biệt giữa chỉ mục phân cụm và không phân cụm, chỉ mục chính và phụ là gì?
• Khi nào thì chỉ mục băm được ưu tiên hơn chỉ mục cây?
• Làm thế nào các chỉ mục tăng tốc các lựa chọn, kết nối và truy xuất có thứ tự?
• Chi phí duy trì chỉ mục khi chèn, cập nhật và xóa là gì?

Key concepts

• Chỉ mục B+-tree
• Chỉ mục băm
• Chỉ mục phân cụm so với không phân cụm
• Chỉ mục chính và phụ
• Chỉ mục dày đặc và thưa thớt
• Tìm kiếm theo phạm vi và bằng
• Băm mở rộng và băm tuyến tính
• Chi phí bảo trì chỉ mục

Key theories

Chỉ mục B+-tree

Cây B+-tree là một cây tìm kiếm cân bằng, có độ phân nhánh cao, lưu trữ các khóa theo thứ tự đã sắp xếp với tất cả các tham chiếu dữ liệu trong các lá; nó hỗ trợ các truy vấn bằng và truy vấn theo phạm vi cũng như quét có thứ tự trong I/O logarit và duy trì cân bằng dưới các thao tác chèn và xóa.

Chỉ mục phân cụm so với không phân cụm

Một chỉ mục phân cụm giữ các hàng của bảng được sắp xếp vật lý theo khóa chỉ mục, làm cho việc quét theo phạm vi rất hiệu quả, trong khi một chỉ mục không phân cụm (thứ cấp) trỏ đến một tệp không có thứ tự, do đó việc truy xuất nhiều hàng phù hợp có thể tốn một I/O cho mỗi hàng.

Chỉ mục băm

Các chỉ mục dựa trên băm ánh xạ các khóa đến các nhóm để tra cứu bằng trong thời gian hằng số dự kiến nhưng không hỗ trợ các truy vấn theo phạm vi; các lược đồ động như băm mở rộng và băm tuyến tính cho phép chúng phát triển linh hoạt theo dữ liệu.

Clinical relevance

Lập chỉ mục là đòn bẩy thực tế phổ biến nhất để cải thiện hiệu suất cơ sở dữ liệu: việc chọn đúng chỉ mục có thể biến các lần quét toàn bộ bảng thành các lần tra cứu trong mili giây cho các truy vấn giao dịch và phân tích, trong khi việc lập chỉ mục quá mức làm chậm các bản cập nhật, do đó thiết kế chỉ mục là một quyết định lặp đi lặp lại trong việc vận hành các hệ thống thực tế.

History

Bayer và McCreight đã giới thiệu cây B-tree vào năm 1972 để duy trì các chỉ mục có thứ tự lớn trên đĩa; biến thể B+-tree, lưu trữ tất cả dữ liệu trong các lá, đã trở thành chỉ mục cơ sở dữ liệu tiêu chuẩn, như được khảo sát trong 'Ubiquitous B-tree' năm 1979 của Comer. Các phương pháp truy cập dựa trên băm và các lược đồ băm động đã phát triển song song, và cả hai họ vẫn là cốt lõi của mọi công cụ quan hệ.

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

Tại sao B+-tree được sử dụng thay vì cây tìm kiếm nhị phân trong cơ sở dữ liệu?

Cơ sở dữ liệu lưu trữ dữ liệu trên đĩa, nơi chi phí bị chi phối bởi số lần đọc trang. B+-tree có độ phân nhánh cao, do đó mỗi nút lấp đầy một trang đĩa và cây rất nông, chỉ yêu cầu một vài I/O để tiếp cận bất kỳ bản ghi nào. Một cây nhị phân sẽ sâu hơn nhiều và gây ra nhiều lần truy cập đĩa hơn.

Khi nào tôi nên sử dụng chỉ mục băm thay vì B+-tree?

Sử dụng chỉ mục băm khi bạn chỉ cần tra cứu bằng (ví dụ: tìm hàng có id nhất định) và muốn truy cập trong thời gian hằng số dự kiến. Sử dụng B+-tree khi bạn cũng cần các truy vấn theo phạm vi, quét có thứ tự hoặc khớp tiền tố, vì chỉ mục băm không duy trì thứ tự khóa và không thể trả lời các điều kiện phạm vi một cách hiệu quả.