PostgreSQL lưu dữ liệu trên đĩa như thế nào?

Ở bài trước, nhờ có index, PostgreSQL chỉ cần truy cập 4 page để tìm chiếc xe mang biển số 25F-950.00 trong bảng có 5 triệu xe.

Trong đó, 3 page thuộc về index. Page thứ tư chứa thông tin của chiếc xe mà chúng ta cần tìm.

Nhưng làm sao PostgreSQL biết chiếc xe nằm ở page nào, khi cả bảng có tới 192.308 page?

Để hiểu điều này, chúng ta cần xem PostgreSQL thực sự lưu dữ liệu như thế nào.

Một bảng được chia thành nhiều page

Khi tạo bảng vehicles và thêm 5 triệu chiếc xe, PostgreSQL lưu dữ liệu của bảng vào các file trên đĩa.

Thay vì đọc từng dòng trực tiếp từ file, PostgreSQL chia dữ liệu thành những khối có kích thước cố định, thường là 8 KB, gọi là page.

Bảng vehicles của chúng ta có 192.308 page, được đánh số từ 0 đến 192.307.

Mỗi page chứa nhiều chiếc xe. Chẳng hạn, page 0 có khoảng 26 chiếc xe đầu tiên.

Nhờ các page được đánh số, PostgreSQL có thể tìm thẳng đến một page bất kỳ mà không phải đọc những page đứng trước nó.

Ví dụ, nếu cần page 192, PostgreSQL biết nó nằm ở vị trí nào trong dữ liệu của bảng và có thể đọc trực tiếp page đó.

Nhưng một page chứa nhiều dòng. Làm sao PostgreSQL biết chiếc xe cần tìm nằm ở vị trí nào bên trong page?

Bên trong một page có gì?

Một page không đơn giản là các dòng dữ liệu xếp liên tiếp nhau.

Ở đầu page, PostgreSQL dành một phần nhỏ để lưu thông tin về page. Ngay sau đó là danh sách con trỏ dòng (line pointer).

Mỗi con trỏ cho biết một dòng dữ liệu nằm ở vị trí nào trong page và chiếm bao nhiêu byte.

PostgreSQL cần những con trỏ này vì các dòng có thể dài ngắn khác nhau. Nó không thể lấy kích thước của một dòng nhân với số thứ tự để tính ra vị trí dòng tiếp theo.

Các con trỏ được xếp từ đầu page xuống, còn dữ liệu của các dòng được đặt từ cuối page lên. Khoảng giữa là chỗ trống dành cho dữ liệu mới.

Đây là cấu trúc page 0 của bảng vehicles, được đọc bằng công cụ pageinspect của PostgreSQL:

Bên trong page 0 của bảng vehicles · 8192 byte

Bấm vào một con trỏ để xem dòng dữ liệu tương ứng.

0

phần đầu page · 24 byte

24

26 con trỏ · 4 byte mỗi con trỏ

1234567891011121314151617181920212223242526

128

trống · 288 byte

416

26 dòng · xếp từ cuối page lên

1. id 26
2. id 25
3. id 24
4. id 23
5. id 22
6. id 21
7. id 20
8. id 19
9. id 18
10. id 17
11. id 16
12. id 15
13. id 14
14. id 13
15. id 12
16. id 11
17. id 10
18. id 9
19. id 8
20. id 7
21. id 6
22. id 5
23. id 4
24. id 3
25. id 2
26. id 1

8192

ctid = (0,3)

Page 0 → Con trỏ 3 → id = 3

dòng bắt đầu ở byte 7304 · dài 296 byte · biển số 10A-237.57

Mỗi con trỏ được đánh số bắt đầu từ 1.

Ví dụ, con trỏ số 3 cho PostgreSQL biết dòng thứ ba bắt đầu ở byte nào và dài bao nhiêu. Nhờ đó, nó có thể lấy đúng dòng cần tìm mà không phải đọc lần lượt các dòng trước đó.

Vậy để xác định vị trí một chiếc xe, PostgreSQL chỉ cần biết hai thông tin:

• Số page: chiếc xe nằm trong page nào.
• Số con trỏ: chiếc xe nằm ở đâu bên trong page đó.

ctid là địa chỉ của một dòng dữ liệu

PostgreSQL gọi cặp số trên là ctid.

Mỗi dòng trong bảng đều có một ctid. Đây là cột hệ thống có sẵn của PostgreSQL, nhưng không xuất hiện khi chúng ta dùng SELECT *.

Thử xem địa chỉ của chiếc xe 25F-950.00:

SELECT ctid, id, plate
FROM vehicles
WHERE id = 5000;

Kết quả trên bộ dữ liệu của chúng ta:

  ctid  |  id  |    plate
--------+------+-------------
(192,8) | 5000 | 25F-950.00

(192,8) có nghĩa là:

• 192: chiếc xe nằm trong page số 192.
• 8: con trỏ số 8 trong page đó chỉ đến dòng chứa chiếc xe.

Vậy là PostgreSQL đã có một địa chỉ cụ thể để tìm chiếc xe.

Nó chỉ cần đọc page 192, tìm con trỏ số 8, rồi lấy dữ liệu tại vị trí mà con trỏ chỉ đến.

Đây cũng chính là thông tin mà index sử dụng.

Khi PostgreSQL tìm biển số 25F-950.00 trong index, nó tìm được địa chỉ (192,8). Từ địa chỉ đó, PostgreSQL truy cập page 192 để lấy thông tin chiếc xe trong bảng.

Đó là lý do ở bài trước, sau khi đi qua 3 page của index, PostgreSQL chỉ cần thêm 1 page của bảng để lấy được chiếc xe.

ctid có cố định không?

Không. ctid là vị trí lưu trữ của một phiên bản dòng dữ liệu, không phải mã định danh cố định của chiếc xe.

Khi thực hiện UPDATE, PostgreSQL tạo một phiên bản mới của dòng thay vì ghi đè trực tiếp lên phiên bản cũ.

Nếu page hiện tại còn đủ chỗ, phiên bản mới có thể được đặt trong cùng page. Nếu không, PostgreSQL phải tìm một page khác còn chỗ trống.

Thử sửa số km của chiếc xe có id = 3:

BEGIN;

SELECT ctid FROM vehicles WHERE id = 3;

UPDATE vehicles
SET mileage_km = mileage_km + 1
WHERE id = 3;

SELECT ctid FROM vehicles WHERE id = 3;

ROLLBACK;

Trước khi sửa, địa chỉ chiếc xe là (0,3).

Trong lần chạy ví dụ này, sau khi sửa, địa chỉ chuyển thành (192307,19). Page 0 không đủ chỗ cho phiên bản mới nên PostgreSQL đặt nó vào một page khác còn chỗ trống.

Địa chỉ mới có thể khác nếu dữ liệu hoặc tình trạng chỗ trống của bảng thay đổi. Lệnh ROLLBACK ở cuối giúp huỷ thao tác sửa thử.

Vì ctid có thể thay đổi sau UPDATE hoặc các thao tác như VACUUM FULL, chúng ta không nên dùng nó để định danh xe. Việc đó vẫn nên dùng khoá chính id.

Vậy index tìm địa chỉ bằng cách nào?

Chúng ta đã biết PostgreSQL lưu bảng thành các page, mỗi page chứa nhiều dòng dữ liệu. Mỗi dòng có một địa chỉ ctid cho biết page nào và con trỏ nào.

Nhưng dữ liệu trong bảng không được tự động sắp xếp theo biển số hay theo id. PostgreSQL lưu các phiên bản dòng vào những vị trí phù hợp, nên không thể nhìn biển số 25F-950.00 mà tự biết nó nằm ở page 192.

Đó là công việc của index.

Index giữ các giá trị cần tìm, chẳng hạn biển số xe, cùng thông tin vị trí của dòng tương ứng trong bảng.

Vấn đề là index của chúng ta cũng chứa hàng triệu biển số. Nếu vẫn phải tìm từng biển số một để lấy ctid, chẳng phải chúng ta lại gặp đúng vấn đề ban đầu sao?

PostgreSQL giải quyết bằng cách tổ chức index thành một cây B-tree.

Vì sao index phải là một cái cây?