Cấu trúc dữ liệu và Giải thuật Bài 78: B-Tree và B+ Tree - Trái tim của mọi Hệ quản trị Cơ sở dữ liệu (DBMS).

Trong suốt 77 bài học qua, chúng ta đã xây dựng vô số cấu trúc dữ liệu chạy trên RAM (Bộ nhớ trong). RAM có tốc độ truy xuất cực nhanh và cho phép nhảy đến bất kỳ địa chỉ ngẫu nhiên nào chỉ trong vài nano-giây. Tuy nhiên, khi Hiếu làm việc với các cơ sở dữ liệu tại Hasaki (như MySQL hay PostgreSQL), dữ liệu không nằm trên RAM mà được lưu trữ vĩnh viễn trên Ổ cứng (Disk / SSD).

Đây là lúc một ranh giới vật lý nghiệt ngã xuất hiện: Tốc độ đọc ngẫu nhiên của ổ cứng chậm hơn RAM hàng chục nghìn lần. Nếu chúng ta sử dụng Cây nhị phân tìm kiếm (như AVL hay Red-Black Tree) để làm Index cho Database, hệ thống sẽ sụp đổ. Để giải quyết bài toán độ trễ vật lý của ổ cứng, giới khoa học máy tính đã phát minh ra một cấu trúc dữ liệu vĩ đại: B-Tree và phiên bản tiến hóa tối thượng của nó là B+ Tree.

1. Điểm mù của Cây Nhị Phân trên Ổ cứng (Disk I/O)

Ổ cứng không đọc từng byte một. Khi bạn yêu cầu đọc 1 byte, hệ điều hành sẽ tải toàn bộ một khối dữ liệu liền kề gọi là Page hoặc Block (thường có kích thước 4KB hoặc 16KB) từ ổ cứng lên RAM. Thao tác này gọi là Disk I/O, và nó vô cùng đắt đỏ.

Nếu bạn lưu 1 triệu bản ghi bằng Cây nhị phân (Binary Tree):

Chiều cao của cây sẽ là $\log_2(1,000,000) \approx 20$ .
Trong trường hợp xấu nhất, để tìm một bản ghi, bạn phải đi từ Root xuống Leaf, đi qua 20 Node.
Vì mỗi Node nằm rải rác ngẫu nhiên trên ổ cứng, bạn sẽ kích hoạt 20 lần Disk I/O. Mỗi lần lấy lên một Block 16KB nhưng lại vứt đi hầu hết, chỉ lấy đúng vài byte chứa Node đó. Đây là sự lãng phí tài nguyên khủng khiếp.

Mục tiêu tối thượng của Database Indexing là: Làm sao để đọc ít Block ổ cứng nhất có thể?

Câu trả lời: Làm cho cái cây "lùn" đi bằng cách nhét thật nhiều dữ liệu vào một Node sao cho kích thước của 1 Node vừa vặn bằng đúng kích thước của 1 Disk Block (16KB). Đó chính là B-Tree.

2. B-Tree: Cây đa phân lấp đầy Disk Block

B-Tree (Balanced Tree) phá vỡ quy tắc "mỗi node chỉ có 2 con" của cây nhị phân. Trong B-Tree bậc $M$ :

Một Node có thể chứa tối đa $M-1$ khóa (Keys) được sắp xếp tăng dần.
Một Node có thể có tối đa $M$ nhánh con (Children).

Sức mạnh của B-Tree:

Giả sử 1 Block của MySQL (InnoDB) là 16KB. Một Node B-Tree có thể chứa tới hàng trăm khóa và con trỏ. Nghĩa là bậc $M$ có thể lên tới hàng trăm.

Với $M = 100$ :

Tầng 0 (Root): 1 Node chứa 100 con trỏ.
Tầng 1: 100 Node, chứa $100 \times 100 = 10,000$ con trỏ.
Tầng 2: 10,000 Node, chứa $10,000 \times 100 = 1,000,000$ bản ghi.

Chỉ với chiều cao cây bằng 3, B-Tree đã có thể chứa 1 triệu bản ghi! Để tìm một dữ liệu bất kỳ trong 1 triệu bản ghi, hệ thống chỉ cần thực hiện tối đa 3 lần Disk I/O (thường Root node đã được cache sẵn trên RAM, nên thực tế chỉ tốn 1-2 lần chạm ổ cứng).

3. B+ Tree: Sự tiến hóa hoàn hảo cho Relational Database

B-Tree rất tuyệt, nhưng nó có một nhược điểm khi xử lý các câu truy vấn thực tế. Tại Hasaki, các truy vấn thường có dạng khoảng (Range Query):

SELECT * FROM orders WHERE created_at BETWEEN '2026-10-01' AND '2026-10-08'

Với B-Tree, việc duyệt các phần tử trong một khoảng giá trị buộc thuật toán phải liên tục nhảy lên nhảy xuống giữa các Node cha và con, gây ra Disk I/O ngẫu nhiên diện rộng. B+ Tree ra đời để giải quyết dứt điểm vấn đề này với 2 cải tiến cốt lõi:

Phân tách định tuyến và dữ liệu: Các Node nội bộ (Internal Nodes) chỉ chứa Khóa (Key) dùng làm "biển báo giao thông" để định tuyến. Toàn bộ dữ liệu thực tế (Data payload / Row pointer) chỉ được lưu trữ ở Nút lá (Leaf Nodes). Điều này giúp Internal Node nhỏ hơn, chứa được nhiều Khóa hơn, làm cây càng "lùn" hơn nữa.
Danh sách liên kết ở đáy: Tất cả các Nút lá được kết nối với nhau thành một Danh sách liên kết kép (Doubly Linked List) nằm ngang.

Khi thực hiện Range Query trên B+ Tree: Hệ thống đi từ Root xuống Leaf để tìm ngày '2026-10-01'. Khi đã chạm đáy, nó không cần nhảy lên xuống nữa, mà chỉ việc "trượt" ngang theo danh sách liên kết cho đến khi gặp '2026-10-08'. Đây là thao tác đọc tuần tự (Sequential Read) — thao tác mà ổ cứng (đặc biệt là SSD) thực hiện nhanh nhất.

4. Mô hình hóa B+ Tree bằng Golang

Việc cài đặt toàn bộ cơ chế tách/gộp (Split/Merge) của B+ Tree tốn hàng ngàn dòng code. Dưới đây là cấu trúc minh họa tư duy thiết kế Node và hàm tìm kiếm cốt lõi của B+ Tree:

package main

import "fmt"

// Định nghĩa một Node trong B+ Tree
type BPlusTreeNode struct {
	IsLeaf   bool
	Keys     []int
	Children []*BPlusTreeNode // Dùng cho Internal Node
	Values   []string         // Dùng cho Leaf Node (Ví dụ: lưu trữ payload)
	Next     *BPlusTreeNode   // Con trỏ Linked List ngang (Chỉ dùng cho Leaf Node)
}

// Cấu trúc B+ Tree
type BPlusTree struct {
	Root *BPlusTreeNode
	M    int // Bậc của cây (Số lượng con tối đa)
}

// Hàm tìm kiếm điểm bắt đầu của một Khóa
func (tree *BPlusTree) Search(key int) string {
	if tree.Root == nil {
		return "Not Found"
	}

	curr := tree.Root
	// 1. Đi từ Root xuống Nút lá (Định tuyến)
	for !curr.IsLeaf {
		idx := 0
		// Tìm nhánh con phù hợp dựa trên các khóa định tuyến
		for idx < len(curr.Keys) && key >= curr.Keys[idx] {
			idx++
		}
		curr = curr.Children[idx]
	}

	// 2. Tìm kiếm tuyến tính (hoặc nhị phân) trong Nút lá
	for i, k := range curr.Keys {
		if k == key {
			return curr.Values[i]
		}
	}
	return "Not Found"
}

// Hàm minh họa Range Query nhờ vào con trỏ Next
func (tree *BPlusTree) RangeQuery(startKey, endKey int) []string {
	var results []string
	if tree.Root == nil {
		return results
	}

	// 1. Định vị điểm bắt đầu (Tương tự hàm Search)
	curr := tree.Root
	for !curr.IsLeaf {
		idx := 0
		for idx < len(curr.Keys) && startKey >= curr.Keys[idx] {
			idx++
		}
		curr = curr.Children[idx]
	}

	// 2. Trượt ngang theo danh sách liên kết để thu thập dữ liệu
	for curr != nil {
		for i, k := range curr.Keys {
			if k >= startKey && k <= endKey {
				results = append(results, curr.Values[i])
			}
			if k > endKey {
				return results // Vượt qua khoảng tìm kiếm, kết thúc sớm
			}
		}
		curr = curr.Next // Quét Block tiếp theo trên ổ cứng
	}

	return results
}

func main() {
	// Giả lập dữ liệu đã được nạp vào B+ Tree (Mô phỏng Index của MySQL)
	leaf2 := &BPlusTreeNode{IsLeaf: true, Keys: []int{50, 60}, Values: []string{"Order_50", "Order_60"}}
	leaf1 := &BPlusTreeNode{IsLeaf: true, Keys: []int{10, 20}, Values: []string{"Order_10", "Order_20"}, Next: leaf2}
	
	root := &BPlusTreeNode{
		IsLeaf:   false,
		Keys:     []int{50}, // Khóa phân tách định tuyến
		Children: []*BPlusTreeNode{leaf1, leaf2},
	}

	tree := &BPlusTree{Root: root, M: 3}

	fmt.Println("Tìm kiếm Key 20:", tree.Search(20))
	fmt.Println("Tìm kiếm Key 99:", tree.Search(99))
	
	fmt.Printf("Range Query [10 -> 50]: %v\n", tree.RangeQuery(10, 50))
}

5. Phân tích Hiệu năng (Big-O) và Kiến trúc Database

Thời gian Truy vấn Điểm (Point Lookup): $O(\log_M N)$ . Với $M$ (bậc) rất lớn, $\log_M N$ có giá trị vô cùng nhỏ, đảm bảo số lần gọi Disk I/O hiếm khi vượt quá $3-4$ lần ngay cả với bảng có hàng tỷ bản ghi.
Thời gian Truy vấn Khoảng (Range Query): $O(\log_M N + K)$ với $K$ là số lượng phần tử trong khoảng cần lấy. Cơ chế trượt ngang qua Leaf Node là điểm chí mạng khiến B+ Tree thống trị tuyệt đối trong thiết kế cơ sở dữ liệu quan hệ (RDBMS).

Ứng dụng cốt lõi:

Trong cơ sở dữ liệu MySQL (Engine InnoDB), Khóa chính (Primary Key) chính là một Clustered B+ Tree. Toàn bộ dữ liệu thật của các cột trong bảng được lưu trữ tại chính phần Nút lá của cây này. Các Index phụ (Secondary Index) cũng là các B+ Tree, nhưng phần lá của chúng không chứa dữ liệu thật mà chứa giá trị của Primary Key, hệ thống sẽ dùng Primary Key đó vòng lại cây chính để tra cứu dữ liệu (Quá trình này gọi là Lookup / Bookmark Lookup).

B+ Tree là tiêu chuẩn vàng cho các hệ thống đọc/ghi cân bằng. Nhưng nếu một hệ thống backend phải nhận hàng triệu lượt GHI mỗi giây (Write-heavy) như lưu log hệ thống hay chuỗi thời gian, việc liên tục chèn và tách Node của B+ Tree trên ổ cứng sẽ tạo ra nút thắt cổ chai trầm trọng. Để giải quyết các hệ thống Big Data này, chúng ta cần một kiến trúc lưu trữ phi quan hệ (NoSQL) hoàn toàn khác.

cấu trúc dữ liệu

1. Điểm mù của Cây Nhị Phân trên Ổ cứng (Disk I/O)

2. B-Tree: Cây đa phân lấp đầy Disk Block

3. B+ Tree: Sự tiến hóa hoàn hảo cho Relational Database

4. Mô hình hóa B+ Tree bằng Golang

5. Phân tích Hiệu năng (Big-O) và Kiến trúc Database

Mục lục