Làm thế nào btree được lưu trữ trên đĩa?

Question

Tôi biết cách triển khai btree trong bộ nhớ, nhưng không rõ về cách lưu trữ btree trong đĩa. Tôi nghĩ có hai khác biệt chính:

1. Chuyển đổi giữa con trỏ bộ nhớ và địa chỉ đĩa, xem post này.
2. Cách tách trang khi chèn mục k/v mới? Nó rất dễ thực hiện trong bộ nhớ.

Cảm ơn

Answer 1

Tôi đề nghị là để có một cái nhìn vào cuốn sách Database System Implementation"

Chương "lưu trữ dữ liệu" 2 và chương 3 "đại diện cho yếu tố dữ liệu" wil cung cấp cho bạn một số gợi ý về vấn đề này.

Cấu trúc chỉ mục của Chương 4 có một phần trên Btrees

Đây là nguồn thông tin tốt nhất mà tôi đã tìm thấy cho đến nay về chủ đề này.

Answer 2

tất cả phụ thuộc vào DBMS bạn sử dụng. Nếu bạn muốn biết nó được thực hiện như thế nào trong MS SQL Server, những điều cần đọc là:

• Trang (tôi đoán chúng gần như tất cả DBMS hiện đại) - trong SQL Server là 8Kb. Tệp cơ sở dữ liệu được tạo từ các trang.
• Mức độ mở rộng - nhóm hợp lý 8 trang liên tục
• (S) GAM - (Bản đồ phân bổ toàn cầu) được chia sẻ. Bitmap chứa thông tin về các phần mở rộng miễn phí và chiếm đóng. Đây là một trong những trang đầu tiên trên tệp cơ sở dữ liệu.
• IAM - Bản đồ phân bổ chỉ mục. Bạn có thể tìm ra chỉ mục/heap nào được lưu trữ trong đó các phần mở rộng. Có thông tin này, bạn có thể lấy vị trí trong tệp nơi lưu trữ chỉ mục/heap.

Sử dụng IAM và GAM (hoặc SGAM), bạn có thể chia trang - chỉ cần di chuyển một phần của trang (được cho là tràn) đến trang khác trong tệp.

IAM và GAM cũng là câu trả lời cho câu hỏi đầu tiên của bạn.

Hầu hết các tên này được lấy từ MS SQL Server nhưng tôi khá chắc chắn, trong DBMS khác, nó được giải quyết khá giống nhau.

Hy vọng điều đó sẽ hữu ích.