DBMS - Lập chỉ mục
Chúng tôi biết rằng dữ liệu được lưu trữ dưới dạng bản ghi. Mỗi bản ghi đều có một trường khóa, giúp nó được nhận dạng duy nhất.
Lập chỉ mục là một kỹ thuật cấu trúc dữ liệu để lấy hiệu quả các bản ghi từ các tệp cơ sở dữ liệu dựa trên một số thuộc tính mà việc lập chỉ mục đã được thực hiện. Việc lập chỉ mục trong các hệ thống cơ sở dữ liệu tương tự như những gì chúng ta thấy trong sách.
Lập chỉ mục được xác định dựa trên các thuộc tính lập chỉ mục của nó. Lập chỉ mục có thể thuộc các loại sau:
Primary Index- Chỉ mục chính được định nghĩa trên tệp dữ liệu có thứ tự. Tệp dữ liệu được sắp xếp theo thứ tựkey field. Trường khóa nói chung là khóa chính của quan hệ.
Secondary Index - Chỉ mục phụ có thể được tạo từ trường là khóa ứng viên và có giá trị duy nhất trong mọi bản ghi hoặc không phải khóa có giá trị trùng lặp.
Clustering Index- Chỉ mục phân cụm được định nghĩa trên tệp dữ liệu có thứ tự. Tệp dữ liệu được sắp xếp trên một trường không phải khóa.
Lập chỉ mục có thứ tự gồm hai loại -
- Chỉ số dày đặc
- Chỉ số thưa thớt
Chỉ số dày đặc
Trong chỉ mục dày đặc, có một bản ghi chỉ mục cho mọi giá trị khóa tìm kiếm trong cơ sở dữ liệu. Điều này làm cho việc tìm kiếm nhanh hơn nhưng cần nhiều không gian hơn để lưu trữ các bản ghi chỉ mục. Các bản ghi chỉ mục chứa giá trị khóa tìm kiếm và một con trỏ đến bản ghi thực trên đĩa.
Chỉ số thưa thớt
Trong chỉ mục thưa thớt, các bản ghi chỉ mục không được tạo cho mọi khóa tìm kiếm. Một bản ghi chỉ mục ở đây chứa một khóa tìm kiếm và một con trỏ thực tế đến dữ liệu trên đĩa. Để tìm kiếm một bản ghi, trước tiên chúng ta tiến hành theo chỉ mục bản ghi và tiếp cận tại vị trí thực của dữ liệu. Nếu dữ liệu chúng tôi đang tìm kiếm không phải là nơi chúng tôi tiếp cận trực tiếp bằng cách theo dõi chỉ mục, thì hệ thống bắt đầu tìm kiếm tuần tự cho đến khi tìm thấy dữ liệu mong muốn.
Chỉ số đa cấp
Bản ghi chỉ mục bao gồm các giá trị khóa tìm kiếm và con trỏ dữ liệu. Chỉ mục đa cấp được lưu trữ trên đĩa cùng với các tệp cơ sở dữ liệu thực tế. Khi kích thước của cơ sở dữ liệu tăng lên, kích thước của các chỉ số cũng vậy. Cần lưu giữ các bản ghi chỉ mục trong bộ nhớ chính để tăng tốc các hoạt động tìm kiếm. Nếu chỉ mục mức đơn được sử dụng, thì chỉ mục kích thước lớn sẽ không thể được giữ trong bộ nhớ, dẫn đến nhiều lần truy cập đĩa.
Chỉ mục đa cấp giúp chia chỉ mục thành nhiều chỉ mục nhỏ hơn để làm cho cấp ngoài cùng nhỏ đến mức có thể lưu trong một khối đĩa duy nhất, có thể dễ dàng lưu trữ ở bất kỳ đâu trong bộ nhớ chính.
B + cây
Cây AB + là cây tìm kiếm nhị phân cân bằng tuân theo định dạng chỉ mục nhiều cấp. Các nút lá của cây B + biểu thị các con trỏ dữ liệu thực tế. Cây B + đảm bảo rằng tất cả các nút lá vẫn ở cùng một chiều cao, do đó cân bằng. Ngoài ra, các nút lá được liên kết bằng danh sách liên kết; do đó, một cây B + có thể hỗ trợ truy cập ngẫu nhiên cũng như truy cập tuần tự.
Cấu trúc của B + Tree
Mọi nút lá đều ở khoảng cách bằng nhau từ nút gốc. AB + cây là thứ tựn Ở đâu nđược cố định cho mọi cây B + .
Internal nodes -
- Các nút bên trong (không phải lá) chứa ít nhất ⌈n / 2⌉ con trỏ, ngoại trừ nút gốc.
- Tối đa, một nút nội bộ có thể chứa n con trỏ.
Leaf nodes -
- Các nút lá chứa ít nhất ⌈n / 2⌉ con trỏ bản ghi và ⌈n / 2⌉ giá trị khóa.
- Tối đa, một nút lá có thể chứa n con trỏ ghi và n các giá trị quan trọng.
- Mỗi nút lá chứa một con trỏ khối P để trỏ đến nút lá tiếp theo và tạo thành một danh sách liên kết.
Chèn cây B +
Các cây B + được điền từ dưới lên và mỗi lần nhập được thực hiện ở nút lá.
- Nếu một nút lá bị tràn -
Chia nút thành hai phần.
Phân vùng tại i = ⌊(m+1)/2⌋.
Đầu tiên i các mục nhập được lưu trữ trong một nút.
Phần còn lại của các mục nhập (i + 1 trở đi) được chuyển đến một nút mới.
ith key được nhân đôi ở cha của lá.
Nếu một nút không phải của lá bị tràn -
Chia nút thành hai phần.
Phân vùng nút tại i = ⌈(m+1)/2⌉.
Mục nhập lên đến i được giữ trong một nút.
Phần còn lại của các mục được chuyển đến một nút mới.
B + Xóa cây
Các mục nhập cây B + bị xóa tại các nút lá.
Mục đích được tìm kiếm và xóa.
Nếu đó là một nút bên trong, hãy xóa và thay thế bằng mục nhập từ vị trí bên trái.
Sau khi xóa, quy trình bên dưới được kiểm tra,
Nếu dòng chảy dưới xảy ra, hãy phân phối các mục nhập từ các nút còn lại cho nó.
Nếu không thể phân phối từ bên trái, thì
Phân phối từ các nút bên phải nó.
Nếu không thể phân phối từ trái hoặc từ phải, thì
Hợp nhất nút với trái và phải với nó.