Câu hỏi vừa rồi chạm đến bản chất của Index, một cấu trúc dữ liệu giúp database nhảy thẳng đến kết quả thay vì duyệt từng dòng. Bài học này sẽ đưa bạn từ bài toán gốc đến cấu trúc hoàn chỉnh, chia thành 3 chặng:
Và có một chi tiết quan trọng nữa: khi ổ cứng đọc, nó không đọc một byte, nó đọc nguyên cả một khối (block), thường là 4KB hoặc 8KB hoặc 16KB. Giống như bạn mở tủ hồ sơ, bạn không lôi ra một tờ giấy, bạn lôi nguyên cả ngăn kéo.
Database cũng vậy, nó đọc dữ liệu theo đơn vị gọi là page (trang), mỗi page thường 4KB đến 16KB. Và đây chính là manh mối quan trọng nhất mà chúng ta sẽ cần để hiểu B-Tree.
1. Đọc disk rất đắt → cần giảm số lần đọc
2. Mỗi lần đọc = đọc nguyên một page → cần tận dụng tối đa mỗi lần đọc
Tấm bản đồ chỉ đường
Hãy tưởng tượng bảng dữ liệu của bạn là một cuốn từ điển khổng lồ nhưng các trang lại bị xáo trộn ngẫu nhiên. Để tìm một từ, bạn buộc phải lật từng trang từ đầu đến cuối (Full Table Scan). Đó là ác mộng về hiệu năng.
Đây là lúc Index xuất hiện như một “vị cứu tinh”.
Về bản chất, khi bạn chạy lệnh CREATE INDEX, database không sắp xếp lại bảng gốc. Thay vào đó, nó âm thầm tạo ra một cấu trúc dữ liệu riêng biệt, một bảng chỉ mục phụ trợ, chỉ chứa cột bạn cần tìm kiếm đã được sắp xếp trật tự, kèm theo một tấm vé chỉ đường (gọi là ROWID trong Oracle database hoặc ctid trong PostgreSQL) trỏ thẳng về dữ liệu gốc.
Hãy nghĩ về Index giống hệt phần Mục lục (Index) ở cuối một cuốn sách giáo khoa:
Tuy nhiên, đừng để phép so sánh trên đánh lừa bạn rằng Index đơn giản.
Sách in là dữ liệu chết: Bạn chỉ làm mục lục một lần duy nhất khi xuất bản.
Database là cơ thể sống: Dữ liệu liên tục biến đổi.
Đây chính là điểm mà bạn cần lưu ý: Mỗi khi bạn INSERT, UPDATE, hay DELETE một dòng trong bảng, database buộc phải lao đi cập nhật lại toàn bộ các Index liên quan ngay lập tức. Bạn nhận được tốc độ đọc siêu nhanh, nhưng phải trả giá bằng công sức bảo trì hệ thống mỗi khi ghi dữ liệu.
Chúng ta đã biết Index lưu gì: key đã sắp xếp + pointer về bảng gốc. Nhưng đó mới chỉ là một nửa câu chuyện. Nửa còn lại, cũng là nửa quyết định hiệu năng, là: dùng cấu trúc dữ liệu nào để tổ chức những key ấy trên disk?
Chúng ta cần một cấu trúc dữ liệu có thể tìm kiếm nhanh trong hàng triệu key đã sắp xếp. Nếu bạn từng học qua môn Cấu trúc dữ liệu & Giải thuật, câu trả lời đầu tiên hiện lên trong đầu gần như chắc chắn là Binary Search Tree (BST), cây nhị phân tìm kiếm. Chia đôi, so sánh, loại nửa còn lại, đơn giản và hiệu quả với độ phức tạp O(log₂n).
Trên lý thuyết, BST là ứng viên hoàn hảo. Nhưng khi đặt nó lên disk thay vì RAM, mọi thứ sụp đổ.
BST thất bại vì lãng phí 99.9% mỗi page. Ý tưởng đã rõ: nhét cho đầy mỗi page với data. Nhưng nhét bằng cách nào?
Phương án hiển nhiên: Sorted Array
Cách đơn giản nhất ai cũng nghĩ đến: xếp tất cả key vào một mảng đã sắp xếp trên disk. Nhưng mỗi lần INSERT, toàn bộ phần tử phía sau phải dịch chuyển giống như chèn một cái tên mới vào giữa cuốn danh bạ điện thoại đã in. Chi phí: O(n) cho mỗi insert.
Sorted array không phải hoàn toàn vô dụng, nó cho phép tìm kiếm cực nhanh nhờ Binary Search (O(log n)). Vấn đề duy nhất là ghi quá chậm (O(n)) vì phải dịch chuyển dữ liệu. Vậy có cách nào vừa tìm nhanh, vừa không phải dịch chuyển hàng loạt khi ghi?
Database giải quyết bằng một ý tưởng then chốt: thay vì ép tất cả vào một mảng khổng lồ, hãy chia nhỏ sorted array thành nhiều page (gọi là leaf node), nối chúng bằng Doubly Linked List để duyệt tuần tự, rồi xây một cây phân cấp (tree) phía trên để tìm nhanh. Kết quả chính là B-Tree, cấu trúc dữ liệu mà hầu hết database hiện đại đều sử dụng.
Ba thành phần này kết hợp lại tạo nên B-Tree. Trong 3 phần tiếp theo, chúng ta sẽ lần lượt “mổ xẻ” từng thành phần để hiểu rõ cách chúng hoạt động.
Ở phần trước, chúng ta đã biết database chia dữ liệu index thành các page nhỏ gọi là leaf node, nơi dữ liệu index thực sự được lưu trữ. Bây giờ hãy “mở nắp” một leaf node ra xem bên trong có gì.
Thứ tự trên 2 cấp độ
Index duy trì thứ tự trên 2 cấp độ đồng thời:
Tiếp tục câu chuyện về những “chiếc hộp” Leaf Node. Nếu Leaf Node là những hòn đảo chứa kho báu, thì Doubly Linked List (Danh sách liên kết đôi) chính là hệ thống cầu nối giúp chúng ta di chuyển giữa các đảo mà không cần quay lại đất liền.
Tại sao database lại chọn kiến trúc này? Dưới đây là 3 lý do “sống còn”:
1. Duyệt tuần tự: Range Query cực nhanh
Đây là lý do quan trọng nhất. Khi bạn viết WHERE price BETWEEN 100 AND 500, database dùng tree để nhảy thẳng tới leaf node chứa giá trị 100. Sau đó, thay vì phải leo ngược lên root để tìm giá trị tiếp theo, nó chỉ cần đi theo con trỏ “next” sang leaf node kế tiếp, cứ thế chạy dọc cho đến khi vượt quá 500.
Không có linked list, mỗi lần muốn sang leaf node kế tiếp, database phải leo ngược lên parent rồi đi xuống lại, có thể tốn nhiều lần disk I/O. Linked list biến thao tác này thành một bước duy nhất.
Sức mạnh của con số
Trong InnoDB (MySQL), mỗi page là 16KB. Mỗi node B-Tree chiếm đúng 16KB, vừa khít một page. Một node internal có thể chứa khoảng 500 đến 1000 key tuỳ kích thước key.
Giả sử mỗi node chứa được khoảng 500 key. Một cây B-Tree 3 tầng có thể chứa:
Và thực tế còn ngon hơn thế: node gốc (root) gần như luôn nằm sẵn trong RAM vì nó được truy cập liên tục. Nên thực tế thường chỉ cần 2 lần đọc disk, đôi khi chỉ 1 lần.
Cấu trúc 3 tầng
B-Tree gồm 3 loại node:
Quy tắc xây dựng B-Tree
Mỗi entry trong branch node chứa giá trị lớn nhất (max key) của leaf node tương ứng bên dưới, kèm con trỏ đến leaf node đó. Ví dụ: leaf node chứa [46, 53, 53] → branch entry = 53.
Tầng branch được xây từ dưới lên: gom tất cả max keys của leaf nodes → tạo branch layer. Nếu branch layer vẫn quá lớn → tạo thêm tầng branch nữa, cho đến khi toàn bộ fit vào 1 node duy nhất = Root Node.
B-Tree Traversal: Ví dụ tìm key = 57
Bước 1: Root Node: [39, 83, 98]
Duyệt: 39 < 57 → tiếp. 83 ≥ 57 → đi theo pointer của 83 xuống branch node giữa.
Bước 2: Branch Node: [46, 53, 57, 83]
Duyệt: 46 < 57 → tiếp. 53 < 57 → tiếp. 57 ≥ 57 → đi theo pointer của 57 xuống leaf node.
Bước 3: Leaf Node: [55, 57, 57]
Tìm thấy 2 entries có key=57! Tổng cộng: chỉ đọc 3 blocks (1 root + 1 branch + 1 leaf).
Trên SSD? Khoảng 0.3ms. Đó là sức mạnh của B-Tree.
Ghép tất cả lại: B-Tree Insert
Qua 3 phần vừa rồi, bạn đã hiểu từng thành phần: Leaf Node chứa data, Doubly Linked List nối chúng lại, và Tree dẫn đường từ trên xuống. Bây giờ hãy xem chúng phối hợp với nhau như thế nào khi INSERT một key mới vào B-Tree:
Tóm lại, B+Tree cải tiến B-Tree thuần ở 2 điểm:
| B-Tree thuần | B+Tree (cái bạn đã học) | |
|---|---|---|
| Linked List giữa leaf? | Không có, phải quay lại parent | Có, Doubly Linked List nối các leaf |
| Data ở đâu? | Mọi node (root, branch, leaf) | Chỉ leaf node |
| Internal node chứa gì? | Key + data → ít key/node | Chỉ key + pointer → nhiều key/node |
| Chiều cao cây? | Cao hơn (ít key → nhiều tầng) | Lùn hơn (nhiều key → ít tầng) |
| Range query | Chậm, leo lên leo xuống tree | Nhanh, lướt theo linked list |
| Database nào dùng? | Hầu như không còn dùng | MySQL, PostgreSQL, SQLite, Oracle... |
Range Query: nơi B+Tree tỏa sáng
Khi bạn viết:
Database tìm leaf node chứa giá trị 100 (chỉ cần 2-3 lần đọc disk nhờ cây lùn), rồi lướt theo linked list qua các leaf liên tiếp cho đến khi vượt quá 500. Toàn bộ quá trình là sequential I/O (tuần tự), nhanh gấp bội so với phải leo lên leo xuống cây như B-Tree thuần.
Hành trình của bài này:Từ câu hỏi “tại sao query chậm?” → hiểu disk I/O là nút thắt → Full Table Scan đọc hết mọi page → BST lãng phí 99.9% mỗi page → xây dựng cấu trúc index từng bước (Leaf Node → Linked List → Tree) → và cuối cùng nhận ra: cái chúng ta xây chính là B+Tree, cấu trúc mà mọi database hiện đại đều dùng.
Disk rất chậm: chậm bao nhiêu?
HDD chậm hơn RAM 100.000 lần. Bài toán cốt lõi: giảm số lần đọc disk.
Ở bài tiếp theo, chúng ta sẽ đi vào thực tế: 3 bước của Index Lookup, khi nào index phản tác dụng, và trade-offs khi đánh index.
SELECT * FROM orders WHERE price BETWEEN 100 AND 500;