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
Bây giờ đến lượt bạn cầm lái. Hãy chọn kích thước bảng và vị trí của dòng khớp, rồi cho hai làn chạy đua với nhau.
Trước khi bấm, hãy tự trả lời trong đầu một câu: nếu dòng cần tìm nằm ngay thứ 5 của bảng 10 triệu dòng, liệu Full Table Scan có nhanh không? Rồi chọn đúng phương án đó và xem điều gì thực sự xảy ra.
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.
Và đây là lúc Index xuất hiện như một “vị cứu tinh” mà bạn đã thấy ở animation phần trên.
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. Phần đọc thì tuyệt vời, binary search, O(log n), nhanh gọn. Nhưng còn khi phải ghi thêm một key mới vào giữa thì sao?
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. Các phần tiếp theo sẽ lần lượt “mổ xẻ” từng thành phần để hiểu rõ cách chúng hoạt động, trước khi ghép tất cả lại thành một cấu trúc hoàn chỉnh.
Ở 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ì.
Video vừa rồi cho bạn thấy cái gì nằm trong một leaf node. Nhưng có một câu hỏi mà chỉ nhìn thì không trả lời được: nhét được bao nhiêu entry vào một page thì đủ? Con số đó có tên là fanout, và nó quyết định cây của bạn cao hay lùn.
Hãy tự tay đổi thông số bên dưới. Hai chiếc hộp giữ nguyên khung để so sánh công bằng, chỉ khác nhau ở mức độ lấp đầy.
Đổi page size và kiểu key, xem page tự đóng gói lại và cây cao lên hay lùn xuống.
Key to hơn → mỗi page nhét được ít entry hơn → fanout giảm → cần nhiều tầng hơn để chứa cùng lượng dữ liệu → mỗi lần tra cứu tốn thêm disk I/O.
Cả chuỗi này bắt nguồn từ đúng một điều đã học ở Phần 1: database đọc theo đơn vị page. Kích thước key nghe như chuyện vặt, nhưng nó lan tới tận số lần chạm đĩa của mọi câu query.
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.
2. Duyệt ngược: một index phục vụ cả hai chiều
3. Chèn và xoá cực rẻ: chỉ cần nối lại con trỏ
Nhớ lại nỗi đau của sorted array ở Phần 5: chèn một giá trị vào giữa là phải dịch chuyển hàng loạt phần tử phía sau, O(n). Linked list không có nỗi đau đó. Muốn chèn một leaf node mới vào giữa hai node cũ, database chỉ việc cắt liên kết cũ rồi nối lại 2 con trỏ, không phải đụng vào bất kỳ node nào khác.
Chi phí là O(1), không đổi dù index đang có 10 leaf node hay 10 triệu. Bấm thử animation dưới đây để xem đúng 2 con trỏ đó được cắt và nối lại như thế nào.
Đến đây bạn đã có một hình dung rất gọn gàng: các leaf node xếp thành hàng, nối nhau bằng linked list, tăng dần từ trái sang phải. Hình dung đó đúng về mặt logic.
Nhưng trên ổ cứng thật thì không có hàng lối nào cả. Đây là phần giải thích vì sao sự lệch pha giữa hai thế giới đó lại quyết định tốc độ của rất nhiều câu query.
Hãy tự tay tạo ra sự hỗn loạn đó. Bấm INSERT 1 dòng vài lần và để ý: mỗi dòng mới rơi vào một block trống bất kỳ, còn cột index bên phải thì lúc nào cũng xếp đúng A → Z.
Sau đó cho đầu đọc chạy theo hai thứ tự khác nhau trên cùng ngần ấy dòng và so quãng đường nó phải di chuyển.
Chèn dòng vào bảng heap, rồi cho đầu đọc chạy theo hai thứ tự khác nhau trên cùng ngần ấy dòng.
Index cho bạn thứ tự logic miễn phí. Nhưng lấy dữ liệu thật thì vẫn phải quay về bảng gốc, nơi các dòng nằm rải rác theo thứ tự chèn. Càng lấy nhiều dòng qua index, càng nhiều cú nhảy ngẫu nhiên trên disk.
Đó là lý do một câu query trả về quá nhiều dòng thì database thà quét thẳng cả bảng còn nhanh hơn là đi qua index. Nghe vô lý, nhưng bạn vừa nhìn thấy con số của nó. Bài 3 chiến thuật Scan sẽ mổ xẻ đúng ngưỡng đánh đổi này.
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.
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 thì sao? Khoảng 0.3ms. Đó là sức mạnh của B-Tree.
Ghép tất cả lại: B-Tree Insert
Qua các 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.
Suốt 10 phần vừa rồi, Index là một thứ trừu tượng: cái cây trong hình vẽ, những chiếc hộp trong animation. Bây giờ bạn sẽ tạo ra nó trên một PostgreSQL thật và nhìn thấy nó tồn tại: nó là một object riêng, nó chiếm bao nhiêu disk, và nó nặng lên thế nào khi key to ra.
Ba điều bạn sẽ tự kiểm chứng, đều là những điều bài học đã hứa: index nằm tách biệt khỏi bảng gốc (Phần 3), key càng to thì index càng nặng (Phần 6), và một index phục vụ được cả hai chiều sắp xếp (Phần 7).
SQL Playground chỉ mở cho học viên đã mua khoá “SQL Nâng Cao”. Khi mua, bạn được chạy trực tiếp query trên PostgreSQL với dataset thật của bài học.
Ở Bước 4, ba index trên cùng một bảng, cùng số dòng lại có dung lượng khác hẳn nhau, chỉ vì kích thước key khác nhau. Và mỗi index trong đó đều sẽ phải được cập nhật mỗi lần bạn INSERT, UPDATE hay DELETE.
Đó chính là cuộc đánh đổi mà bài tiếp theo sẽ đo đếm sòng phẳng: Cái giá của Index. Còn cách bắt database khai ra nó đã chọn chiến thuật nào để chạy query, bằng lệnh EXPLAIN, sẽ là nội dung bài Equality & EXPLAIN Plan.
10 câu dưới đây không hỏi bạn nhớ được con số nào, mà hỏi bạn có dùng được những gì vừa học để suy luận ra câu trả lời hay không. Làm hết một lượt rồi xem phần giải thích của những câu sai.
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;