Cấu trúc chỉ mục Firebird cho Firebird 2.0 (ODS 11 trở lên)
Cấu trúc chỉ mục Firebird ODS11 trở lên
Lý do cho cấu trúc mới là:
- hỗ trợ tốt hơn cho việc xóa một khóa chỉ mục trong số nhiều bản sao (gây ra việc dọn rác chậm)
- hỗ trợ số bản ghi lớn hơn 32-bit (40 bit)
- tăng kích thước khóa chỉ mục (1/4 kích thước trang)
Cấu trúc hiện tại (ODS10 trở xuống):
| header | node | node | node | node | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
header =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // trang anh em bên phải
SLONG btr\_left\_sibling; // trang anh em bên trái
SLONG btr\_prefix\_total; // tổng tất cả các tiền tố trên trang
USHORT btr\_relation; // id quan hệ để đảm bảo nhất quán
USHORT btr\_length; // độ dài dữ liệu trong bucket
UCHAR btr\_id; // id chỉ mục để đảm bảo nhất quán
UCHAR btr\_level; // cấp chỉ mục (0 = lá)
struct btn btr\_nodes\[1.;
};
node =
struct btn {
UCHAR btn\_prefix; // kích thước tiền tố đã nén
UCHAR btn\_length; // độ dài dữ liệu trong node
UCHAR btn\_number\[4.; // số trang hoặc số bản ghi
UCHAR btn\_data\[1.;
};
end marker = END_BUCKET hoặc END_LEVEL
Các giá trị này được dùng thay cho số bản ghi đối với node lá và thay cho số trang đối với node không phải lá.
Nếu node là marker END_BUCKET thì nó phải chứa cùng dữ liệu với node đầu tiên trên trang anh em kế tiếp.
Với marker END_LEVEL, prefix và length bằng 0, do đó không chứa dữ liệu.
Ngoài ra, mọi node đầu tiên trên một cấp (trừ trang lá) đều chứa một node có độ dài bằng 0 thoái hóa.
Cấu trúc ODS11 mới:
| header | jump info | jump nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
jump info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // offset đến node đầu tiên trong trang \[\*\]
USHORT jumpAreaSize; // kích thước vùng trước khi tạo một jump node mới
UCHAR jumpers; // số jump node trong trang, tối đa 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // con trỏ đến nơi có thể đọc node này từ trang
USHORT prefix; // độ dài tiền tố so với jump node trước đó
USHORT length; // độ dài dữ liệu trong jump node (cùng với prefix đây là tiền tố cho node trỏ tới)
USHORT offset; // offset đến node trong trang
UCHAR\* data; // Dữ liệu có thể được đọc từ đây
};
Cờ mới cho cấu trúc chỉ mục mới:
Các cờ mới được thêm vào header->pag_flags.
Cờ btr_large_keys (32) dùng để lưu trữ độ dài/tiền tố đã nén và số bản ghi. Điều này cũng có nghĩa là độ dài và tiền tố có thể lên tới 1/4 kích thước trang (1024 cho kích thước trang 4096) và dễ dàng mở rộng trong tương lai mà không cần thay đổi cấu trúc đĩa lần nữa. Số bản ghi cũng có thể dễ dàng mở rộng lên ví dụ 40 bit. Các số này được lưu theo từng 7 bit với 1 bit (cao nhất) làm marker (mã hóa độ dài biến thiên). Mỗi byte mới cần lưu trữ được dịch chuyển 7 bit. Ví dụ: 25 được lưu dưới dạng 1 byte 0x19, 130 = 2 byte 0x82 0x01, 65535 = 3 byte 0xFF 0xFF 0x03.
Node trùng lặp:
Một cờ mới cũng được thêm để lưu số bản ghi trên mọi node (trang không phải lá). Điều này tăng tốc độ truy xuất chỉ mục khi có nhiều bản sao. Cờ này là btr_all_recordnumber (16). Với thông tin bổ sung này, việc tra cứu khóa khi chèn/xóa với nhiều bản sao (NULL trong khóa ngoại chẳng hạn) trở nên nhanh hơn nhiều (chẳng hạn như việc dọn rác!). Bên cạnh đó, các node trùng lặp (length = 0) không lưu thông tin độ dài của chúng, 3 bit từ byte đầu tiên được lưu được dùng để xác định node này có phải là node trùng lặp hay không. Bên cạnh ZERO_LENGTH (4) còn có các marker END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) và ONE_LENGTH (5). Số 6 và 7 được dành cho sử dụng trong tương lai.
Jump node:
Jump node là một tham chiếu đến một node ở đâu đó trong trang.
Nó chứa thông tin offset về node cụ thể và dữ liệu tiền tố từ node được tham chiếu, nhưng trên chính jump node cũng có nén tiền tố.
Lý tưởng nhất là một jump node mới được tạo sau node đầu tiên được tìm thấy sau mỗi jumpAreaSize, nhưng điều đó chỉ xảy ra khi hủy kích hoạt/kích hoạt chỉ mục hoặc chèn các node theo cùng thứ tự mà chúng sẽ được lưu trong chỉ mục.
Nếu các node được chèn giữa hai tham chiếu jump node, chỉ có các offset được cập nhật, nhưng chỉ khi các offset không vượt quá một ngưỡng cụ thể (+/-10 %).
Khi một node bị xóa, chỉ có các offset được cập nhật hoặc một jump node bị loại bỏ. Điều này có nghĩa là có thể tồn tại một khoảng trống nhỏ giữa jump node cuối cùng và node đầu tiên, vì vậy chúng ta không lãng phí thời gian để tạo jump node mới.
Prefix và length cũng được lưu bằng mã hóa độ dài biến thiên.
Dữ liệu ví dụ:
(x) = kích thước tính bằng x byte
| header (34) | ||||
| 52 (2) | 256 (2) | 2 (1) | 30 (2) | 0 (1) |
| 2 (1) | 260 (2) | FI (2) | 1 (1) | 1 (1) |
| 514 (2) | U (1) | 0 (1) | 1 (1) | 0 (1) |
| A (1) | … | |||
| 2 (1) | 6 (1) | 21386 (3) | REBIRD (6) | … |
| 2 (1) | 2 (1) | 1294 (2) | EL (2) | … |
Con trỏ sau header cố định = 0x22
Con trỏ sau jump info = 0x29
Con trỏ đến jump node đầu tiên = 0x29 + 6 (jump node 1) + 5 (jump node 2) = 0x34
Jump node 1 tham chiếu đến node đại diện cho FIREBIRD dưới dạng dữ liệu, vì node này có prefix là 2 nên 2 ký tự đầu FI cũng được lưu trên jump node.
Jump node tiếp theo của chúng ta trỏ đến một node đại diện cho FUEL cũng có prefix là 2. Do đó jump node 2 phải chứa FU, nhưng node trước đó của chúng ta đã chứa F nên do nén tiền tố, ký tự này bị bỏ qua và chỉ có U được lưu.
Trạng thái NULL:
Dữ liệu cần lưu trữ được xác định trong thủ tục compress() trong btr.cpp.
Đối với chỉ mục ASC (tăng dần), không có dữ liệu nào được lưu (khóa có độ dài bằng 0). Điều này tự động đưa chúng vào vị trí đầu tiên trong chỉ mục và do đó đúng thứ tự (Đối với chỉ mục một trường, độ dài node và prefix bằng 0).
Chỉ mục DESC (giảm dần) sẽ lưu một byte duy nhất có giá trị 0xFF (255). Để phân biệt giữa một giá trị (chuỗi rỗng có thể là 255) và trạng thái NULL, chúng ta chèn một byte 0xFE (254) vào đầu dữ liệu. Việc này chỉ được thực hiện cho các giá trị bắt đầu bằng 0xFF (255) hoặc 0xFE (254), để giữ đúng thứ tự.
Ví dụ:
| node chỉ mục ASC, 1 phân đoạn | |||
| prefix | length | dữ liệu lưu trữ | giá trị/trạng thái thực |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| node chỉ mục DESC, 1 phân đoạn | |||
| prefix | length | dữ liệu lưu trữ | giá trị/trạng thái thực |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| node chỉ mục ASC, 3 phân đoạn | |||
| prefix | length | dữ liệu lưu trữ | giá trị/trạng thái thực |
| 0 | 0 | NULL,NULL, NULL | |
| 0 | 10 | x01(1) x70(F) x73(I) x82(R) x69(E) x01(1) x66(B) x73(I) x82(R) x68(D) | NULL, NULL, FIREBIRD |
| 0 | 10 | x02(2) x70(F) x73(I) x82(R) x69(E) x02(2) x66(B) x73(I) x82(R) x68(D) | NULL, FIREBIRD, NULL |
| 0 | 10 | x03(3) x70(F) x73(I) x82(R) x69(E) x03(3) x66(B) x73(I) x82(R) x68(D) | FIREBIRD, NULL, NULL |
| 3 | 9 | x00(0) x00(0) x02(2) x65(A) x00(0) x00(0) x00(0) x01(1) x66(B) | FI, A, B |
| … | … | … | … |
| node chỉ mục DESC, 3 phân đoạn | |||
| prefix | length | dữ liệu lưu trữ | giá trị/trạng thái thực |
| 0 | 12 | xFC xB9 xB6 xFF xFF xFD xBE xFF xFF xFF xFE xBD | FI, A, B |
| 3 | 17 | xAD xBA xFC xBD xB6 xAD xBB xFD xFF xFF xFF xFF xFE xFF xFF xFF xFF | FIREBIRD, NULL, NULL |
| 1 | 19 | xFF xFF xFF xFF xFD xB9 xB6 xAD xBA xFD xBD xB6 xAD xBB xFE xFF xFF xFF xFF | NULL, FIREBIRD, NULL |
| 6 | 14 | xFF xFF xFF xFF xFE xB9 xB6 xAD xBA xFE xBD xB6 xAD xBB | NULL, NULL, FIREBIRD |
| 11 | 4 | xFF xFF xFF xFF | NULL,NULL, NULL |
| END_LEVEL |
c ABVisie 2005, Arno Brinkman