PostgreSQL sử dụng B-tree làm index như thế nào?

Trong PostgreSQL, B-tree được lưu thành một file index gồm nhiều page. Index trên 5 triệu biển số của chúng ta có hơn 19.000 page, nhưng khi tìm một biển số, PostgreSQL chỉ cần đi qua 3 page.

Làm sao nó biết phải đọc những page nào?

Mỗi nút B-tree là một page

Index vehicles_plate_idx được lưu riêng với bảng vehicles. Trong bộ dữ liệu của chúng ta, index chiếm khoảng 150 MB, gồm 19.255 page, mỗi page 8 KB.

Các nút gốc (root), nút trong (internal) và nút lá (leaf) mà chúng ta đã học thực chất đều nằm trong những page này.

• Page gốc và page trong: giữ các key ranh giới và số page con, giúp PostgreSQL biết phải đi đâu tiếp.
• Page lá: giữ biển số cùng địa chỉ dòng tương ứng trong bảng vehicles.

Như vậy, PostgreSQL không cần đọc toàn bộ 19.255 page. Nó bắt đầu từ root, rồi lần theo các page con cho đến khi gặp biển số cần tìm.

PostgreSQL biết root nằm ở đâu?

Muốn tìm kiếm trong B-tree, PostgreSQL cần biết nút gốc nằm ở page nào.

Các page trong file index được đánh số bắt đầu từ 0. PostgreSQL dành page 0 để lưu thông tin về cây, trong đó có vị trí của root. Page đặc biệt này gọi là metapage.

Chúng ta có thể kiểm tra bằng pageinspect:

SELECT root, level
FROM bt_metap('vehicles_plate_idx');

Kết quả:

 root | level
------+-------
  209 |     2

Nghĩa là root nằm ở page 209. Còn level = 2 cho biết bên dưới root có thêm hai tầng, tổng cộng cây có ba tầng.

Page 0 chỉ lưu thông tin về cây, không phải một tầng của B-tree. PostgreSQL cũng có thể giữ thông tin này trong bộ nhớ, thay vì phải đọc lại metapage mỗi lần tìm kiếm.

Tìm một biển số qua các page

Giả sử chúng ta tìm biển số 47P-600.55:

SELECT *
FROM vehicles
WHERE plate = '47P-600.55';

Hãy xem PostgreSQL đi qua những page nào để tìm biển số này.

Một biển số nằm ở đâu trong B-tree index?

Sơ đồ rút gọn, chỉ hiển thị một số page.

Theo dõi cách PostgreSQL tìm biển số 47P-600.55 qua các page.

Bắt đầu

Trong bộ dữ liệu ví dụ, đường tìm kiếm đi qua ba page:

Page 209 → Page 7961 → Page 8059

Ở page 209, PostgreSQL so sánh biển số cần tìm với các key ranh giới và chọn page con 7961.

Page 7961 tiếp tục dẫn tới page lá 8059.

Tại đây, PostgreSQL tìm thấy mục index:

47P-600.55 → (474,21)

Hai loại địa chỉ này có ý nghĩa khác nhau:

• 8059: số page chứa biển số trong file index.
• (474,21): địa chỉ dòng tương ứng trong bảng vehicles.

Nhờ các page được tổ chức thành B-tree, PostgreSQL chỉ cần đi qua một page ở mỗi tầng để tìm tới đúng mục index, thay vì kiểm tra hàng nghìn page lá.

Đi qua ba page cũng không nhất thiết là ba lần đọc đĩa, vì các page có thể đã nằm trong bộ nhớ đệm.

Các page lá nối với nhau ra sao?

Ngoài số page con, PostgreSQL còn lưu thông tin về các page nằm bên cạnh.

Ví dụ, page lá 8059 ghi:

8058 ← 8059 → 8060

Điều này cho phép PostgreSQL chuyển từ page lá này sang page lá kế tiếp để đọc các biển số theo thứ tự, như cách chúng ta đã thấy trong bài về B-tree.

Các số page không nhất thiết phải liên tiếp. PostgreSQL dựa vào liên kết được lưu trong page để biết page bên cạnh nằm ở đâu.

Tìm được địa chỉ dòng rồi thì sao?

Index đã tìm được biển số 47P-600.55 và địa chỉ (474,21).

Nhưng nếu câu SQL yêu cầu SELECT *, PostgreSQL còn phải lấy hãng xe, đời xe, giá bán và những thông tin khác từ bảng vehicles.

Vậy (474,21) có nghĩa là gì, và PostgreSQL dùng nó để tìm đúng dòng dữ liệu như thế nào?

Có địa chỉ dòng rồi, PostgreSQL lấy cả dòng thế nào?