B-tree là gì?

B-tree là một cấu trúc dữ liệu dạng cây, trong đó các key được sắp xếp theo thứ tự để có thể tìm kiếm nhanh chóng. Thay vì đặt tất cả key vào một danh sách dài, B-tree chia chúng thành nhiều nút (node), tổ chức thành các tầng và liên kết với nhau.

Điểm đặc biệt là một nút có thể dẫn tới nhiều nhánh, không chỉ hai nhánh như cây nhị phân (binary tree). B-tree còn là một cây cân bằng (balanced tree), nghĩa là mọi nút lá đều nằm ở cùng một độ sâu.

PostgreSQL sử dụng B-tree làm loại index mặc định. Với index trên cột plate của bảng vehicles, B-tree giúp PostgreSQL tìm một biển số giữa hàng triệu biển số mà không cần kiểm tra lần lượt từng dòng trong bảng.

Một cây B-tree trông như thế nào?

Đây là mô hình đơn giản của một B-tree có ba tầng. Chúng ta dùng các con số thay cho biển số xe để dễ quan sát.

Cấu trúc một B-tree

Nhìn từ trên xuống, cây gồm ba loại nút:

• Nút gốc (root): nằm trên cùng, là nơi bắt đầu mỗi lần tìm kiếm.
• Nút trong (internal node): chứa các key ranh giới để xác định phải đi xuống nhánh nào.
• Nút lá (leaf): nằm ở tầng cuối cùng, chứa những mục mà index cần tìm.

Hãy nhìn vào nút gốc [40 | 70]. Hai key này chia dữ liệu thành ba nhánh: nhỏ hơn 40, từ 40 đến dưới 70, và từ 70 trở lên.

Ở nhánh giữa, nút [50] lại chia dữ liệu thành hai khoảng nhỏ hơn. Những key dưới 50 nằm ở lá bên trái, còn từ 50 trở lên nằm ở lá bên phải.

Các giá trị 40, 50 và 70 đóng vai trò key ranh giới (separator key). Chúng giúp B-tree xác định một giá trị cần tìm có thể nằm ở đâu.

Trong mỗi nút, các key được sắp xếp theo thứ tự. Mọi lá đều nằm ở tầng cuối cùng, dù chúng thuộc nhánh nào.

Trong PostgreSQL, những nút phía trên chủ yếu phục vụ việc định hướng tìm kiếm. Các nút lá chứa những mục index thực sự, gồm key và thông tin giúp xác định dòng tương ứng trong bảng.

B-tree tìm một giá trị như thế nào?

Giả sử cần tìm key 54 trong một cây B-tree. Hãy theo dõi đường đi từ nút gốc xuống nút lá.

Tìm giá trị trong B-tree

Giá trị cần tìm Bắt đầu

1. Gốc
2. Nút trong
3. Lá

Chưa bắt đầu

Bấm Bắt đầu để đi từ gốc xuống, mỗi lần một tầng.

B-tree bắt đầu tại nút gốc [40]. Vì 54 lớn hơn 40, nó bỏ qua toàn bộ nhánh bên trái và đi sang phải.

Tại nút [50 | 70], 54 nằm giữa 50 và 70, nên cây chọn nhánh giữa. Cuối cùng, nó đến lá [50, 54, 58] và tìm thấy 54.

Cây trong ví dụ có tổng cộng 8 nút, nhưng việc tìm kiếm chỉ cần đi qua 3 nút.

Thử đổi giá trị cần tìm thành 55. B-tree vẫn đi đến lá [50, 54, 58], nhưng lần này không tìm thấy kết quả. Vì các key đã được sắp xếp, 55 không thể nằm ở nhánh nào khác.

Mỗi lần đi xuống một tầng, B-tree chỉ chọn một nhánh và bỏ qua những nhánh không liên quan. Đó là nguyên lý giúp nó tìm kiếm nhanh.

Với PostgreSQL, một truy vấn như:

SELECT *
FROM vehicles
WHERE plate = 'ABC123';

có thể sử dụng B-tree index trên plate để tìm entry tương ứng. Từ entry đó, PostgreSQL xác định vị trí dòng cần đọc trong bảng.

Database không phải duyệt qua 5 triệu dòng để tìm một biển số. Nó đi qua một số ít nút của index để tìm đến đúng vị trí.

Vì sao hàng triệu key chỉ cần vài tầng?

Trong các hình minh họa, một nút chỉ chứa vài key. Nhưng B-tree trong PostgreSQL có thể chứa hàng trăm key trong một nút.

Mỗi nút tương ứng với một page, thường có kích thước 8 KB. Thay vì dành cả một page cho một key, B-tree tận dụng không gian đó để lưu nhiều key và thông tin dẫn tới nhiều nút con.

Càng có nhiều nhánh ở mỗi nút, cây càng cần ít tầng để chứa cùng một lượng dữ liệu.

Giả sử mỗi nút trong có thể dẫn tới 200 nút con và mỗi lá giữ 200 mục. Khi đó một cây có:

• 1 tầng: chứa được 200 key.
• 2 tầng: chứa được 40.000 key.
• 3 tầng: chứa được 8 triệu key.

Chỉ thêm một tầng, sức chứa trong mô hình này đã tăng khoảng 200 lần.

Số tầng phải đi qua để tìm một key

1. 1 nghìn key

   Cây nhị phân, 2 nhánh10 tầng

   B-tree, ~200 nhánh2 tầng

2. 1 triệu key

   Cây nhị phân, 2 nhánh20 tầng

   B-tree, ~200 nhánh3 tầng

3. 5 triệu keycỡ bảng vehicles

   Cây nhị phân, 2 nhánh23 tầng

   B-tree, ~200 nhánh3 tầng

4. 1 tỷ key

   Cây nhị phân, 2 nhánh30 tầng

   B-tree, ~200 nhánh4 tầng

Với 5 triệu key, một cây nhị phân cân bằng cần khoảng 23 tầng để tìm tới một key ở độ sâu lớn nhất. Trong mô hình B-tree có 200 nhánh vừa tính, ba tầng đã đủ sức chứa.

Đó là lợi thế rất lớn khi index nằm trên hệ thống lưu trữ. Tìm kiếm chỉ cần đi qua một số ít page, thay vì phải lần lượt kiểm tra rất nhiều page khác nhau.

Con số 200 chỉ là ví dụ để dễ tính. Số key và số nhánh thực tế phụ thuộc vào kích thước của mỗi entry và dung lượng còn trống trong page.

Ở ví dụ vehicles_plate_idx đã đo bằng pageinspect trong bài trước, mỗi page lá chứa trung bình khoảng 262 mục, còn mỗi page trong có khoảng 200 key ranh giới. Cây index có ba tầng.

Đi qua ba tầng nghĩa là truy cập ba page của index, nhưng không nhất thiết phải đọc đĩa ba lần. PostgreSQL có thể đã giữ những page thường xuyên sử dụng trong bộ nhớ đệm (buffer cache).

Nhờ mỗi nút có nhiều nhánh, B-tree có thể chứa hàng triệu key mà cây vẫn rất thấp.

Khi thêm dữ liệu mới, B-tree thay đổi như thế nào?

Tìm kiếm nhanh là một chuyện. Database còn phải liên tục thêm dữ liệu mà vẫn giữ index theo thứ tự.

Nếu lưu toàn bộ key trong một mảng liên tục đã sắp xếp, việc tìm kiếm bằng binary search khá nhanh. Nhưng khi chèn một key vào giữa mảng, có thể phải dịch chuyển rất nhiều phần tử phía sau để tạo chỗ trống.

B-tree không cần làm như vậy. Các key được chia thành nhiều nút, nên một lần thêm dữ liệu thường chỉ ảnh hưởng đến một phần nhỏ của cây.

Giả sử một nút lá đang chứa [10, 20, 30], và trong mô hình này mỗi lá chỉ được giữ tối đa ba key.

Điều gì xảy ra khi thêm 25?

Thêm 25

Lá trái đã đủ 3 key

B-tree tìm đến lá chứa khoảng giá trị thích hợp rồi chèn 25 vào giữa 20 và 30.

Lá lúc này có bốn key [10, 20, 25, 30], vượt quá sức chứa. B-tree giải quyết bằng cách tách nút (split) thành hai lá: [10, 20] và [25, 30].

Nút cha được cập nhật thêm key ranh giới 25 và liên kết tới lá mới. Những lá ở các nhánh khác không cần dịch chuyển.

Nếu lá vẫn còn đủ chỗ, việc thêm key đơn giản hơn nhiều và không cần split.

Nếu nút cha cũng hết chỗ, quá trình tách có thể tiếp tục lên tầng trên. Khi nút gốc phải tách, cây tạo một gốc mới và cao thêm một tầng.

Cây luôn giữ mọi lá ở cùng một độ sâu. Vì vậy, dù liên tục thêm key theo thứ tự tăng dần, B-tree cũng không biến thành một nhánh dài.

Trong PostgreSQL thực tế, giới hạn của một nút được tính theo dung lượng page, không phải một số key cố định như ví dụ. Nhưng nguyên lý vẫn vậy: khi không còn đủ chỗ, B-tree có thể tách page để tiếp tục nhận dữ liệu.

Nhờ đó, B-tree vừa duy trì được thứ tự key để tìm kiếm, vừa có thể phát triển khi bảng ngày càng lớn mà không phải sắp xếp lại toàn bộ index sau mỗi lần thêm dữ liệu.

B-tree tìm cả một khoảng giá trị như thế nào?

B-tree không chỉ tìm được một key cụ thể. Vì các key đã được sắp xếp, nó còn có thể tìm hiệu quả tất cả các key trong một khoảng.

Giả sử cần tìm những giá trị từ 42 đến 57.

Đọc một khoảng giá trị trong B-tree

WHERE key BETWEEN 42 AND 57

Chưa bắt đầu

Bấm Bắt đầu để xem B-tree đọc khoảng này qua từng bước.

Kết quả

1. chưa có key nào

Bắt đầu

B-tree đi từ gốc xuống lá chứa điểm bắt đầu là 42, giống như khi tìm một key thông thường.

Nhưng thay vì dừng lại sau khi tìm được 42, nó tiếp tục đọc các giá trị theo thứ tự.

Ở lá đầu tiên, cây lấy được 42 và 47. Sau đó, nó chuyển sang lá kế bên, đọc tiếp 50 và 54. Gặp 58, lớn hơn giới hạn 57, quá trình dừng lại.

Kết quả là [42, 47, 50, 54].

Điểm đáng chú ý là B-tree không cần quay lại gốc để tìm từng key tiếp theo.

Các page lá của B-tree trong PostgreSQL có liên kết với những page bên cạnh, gọi là sibling links. Nhờ vậy, sau khi tìm được vị trí bắt đầu, database có thể đọc tiếp các page lá theo thứ tự.

Đây là lý do B-tree hỗ trợ cả tìm kiếm chính xác bằng = lẫn truy vấn theo khoảng bằng <, >, BETWEEN.

Chẳng hạn, để tìm những biển số nằm trong một khoảng:

SELECT *
FROM vehicles
WHERE plate BETWEEN 'ABC100' AND 'ABC200';

Nếu PostgreSQL chọn sử dụng B-tree index, nó có thể tìm vị trí của 'ABC100', sau đó đọc tiếp các entry cho đến khi vượt qua 'ABC200'.

Thay vì thực hiện một lần tìm kiếm riêng cho từng biển số, PostgreSQL tận dụng thứ tự của các key và liên kết giữa những page lá.

Điều này cũng giải thích vì sao B-tree được PostgreSQL chọn làm index mặc định: nó phù hợp với cả những truy vấn tìm một giá trị lẫn những truy vấn đọc một khoảng giá trị.

Vậy PostgreSQL tổ chức những page đó ra sao, và làm cách nào nó biết phải đọc page nào tiếp theo?