Cấu trúc dữ liệu và Giải thuật Bài 84: Radix Tree (Cây cơ số) - Nền tảng định tuyến siêu tốc trong các HTTP Router hiện đại.

viết API bằng các framework như Laravel (PHP), Express (Node.js) hay Gin/Echo (Golang), bạn thường định nghĩa hàng chục, thậm chí hàng trăm endpoints:

• GET /api/v1/users

• GET /api/v1/users/:id

• POST /api/v1/users/:id/orders

• GET /api/v1/products/search

Khi một HTTP Request bay vào server với đường dẫn /api/v1/users/102/orders, làm sao framework biết chính xác phải gọi đến Controller hay Closure (Handler) nào?

Nếu dùng một mảng (Array) chứa các Regex (Biểu thức chính quy) và quét tuần tự từ trên xuống dưới, hệ thống sẽ chậm dần khi số lượng API tăng lên (độ phức tạp $O(N)$). Để đạt tốc độ truy xuất $O(K)$ (với $K$ là độ dài của URL) — không bị ảnh hưởng bởi số lượng API trong hệ thống — các framework hiện đại sử dụng một phiên bản nén của Cây Trie (Bài 52) mang tên Radix Tree (Cây cơ số, hay còn gọi là Patricia Trie).

1. Nỗi đau của Standard Trie và Sự ra đời của Radix Tree

Trong một Standard Trie (Cây tiền tố cơ bản), mỗi Node chỉ lưu trữ đúng 1 ký tự.

Nếu bạn chèn 2 chuỗi /api/v1/users và /api/v1/posts, Trie sẽ tạo ra hàng loạt các Node nối đuôi nhau một cách vô nghĩa:

(Root) -> / -> a -> p -> i -> / -> v -> 1 -> / -> ...

Việc tạo ra 10 Node liên tiếp chỉ có đúng 1 nhánh con (Single-child nodes) gây ra hai vấn đề:

1. Lãng phí RAM trầm trọng: Hàng ngàn Node được tạo ra chỉ để chứa các ký tự trùng lặp.

2. Chậm chạp (Cache Miss): Cứ đọc 1 ký tự lại phải nhảy con trỏ sang vùng nhớ khác trên RAM.

Radix Tree giải quyết bằng cơ chế Nén (Compression):

Bất kỳ chuỗi Node nào có duy nhất một nhánh con kéo dài sẽ được gộp lại (Merge) thành một Node duy nhất chứa một chuỗi ký tự (String/Edge Label).

Ví dụ, với 2 route trên, Radix Tree sẽ chỉ có:

• Root Node chứa: /api/v1/

• Rẽ nhánh 1: users

• Rẽ nhánh 2: posts

Nhờ việc gộp này, cấu trúc cây trở nên cực kỳ nông (shallow), tiết kiệm 80% RAM và tăng tốc độ duyệt nhờ cơ chế đối chiếu một lúc nhiều ký tự thay vì từng ký tự đơn lẻ.

2. Bắt các Biến động (Dynamic Parameters) và Wildcards

HTTP Router không chỉ có các chuỗi tĩnh (Static Routes) mà còn có các biến động (Parametric Routes) như :id.

Để hỗ trợ điều này, mỗi Node trong Radix Tree của một Router thường được phân loại (NodeType):

• Static Node: Khớp chính xác chuỗi (VD: /users/).

• Param Node: Khớp một phân đoạn động, dừng lại khi gặp dấu / tiếp theo (VD: :id).

• Catch-all / Wildcard Node: Khớp toàn bộ phần đuôi còn lại của URL (VD: *filepath).

Khi rẽ nhánh, thuật toán tìm kiếm trên Radix Tree sẽ luôn ưu tiên Static Node trước. Nếu không tìm thấy, nó sẽ lùi lại (Backtrack) và thử đi vào Param Node. Cơ chế này đảm bảo /users/search sẽ gọi đúng hàm tìm kiếm, thay vì hiểu nhầm chữ search thành :id trong /users/:id.

3. Triển khai Radix Tree Router siêu tốc bằng Golang

Hệ sinh thái Golang nổi tiếng với hiệu năng cao, và package julienschmidt/httprouter hay gin-gonic/gin đều sử dụng Radix Tree làm lõi.

Dưới đây là phiên bản minh họa (đã đơn giản hóa) cách một Radix Tree chèn URL tĩnh và nén chuỗi:

Go

package main

import (
	"fmt"
	"strings"
)

// Cấu trúc một Node trong Radix Tree
type RadixNode struct {
	path     string       // Chuỗi ký tự (Edge label) đã được nén
	handler  string       // Tên của Controller (Nếu là điểm kết thúc của một Route)
	children []*RadixNode // Các nhánh con
}

type RadixTree struct {
	root *RadixNode
}

func NewRadixTree() *RadixTree {
	return &RadixTree{
		root: &RadixNode{path: ""},
	}
}

// Hàm tìm độ dài tiền tố chung (Longest Common Prefix) giữa 2 chuỗi
func longestCommonPrefix(a, b string) int {
	i := 0
	max := len(a)
	if len(b) < max {
		max = len(b)
	}
	for i < max && a[i] == b[i] {
		i++
	}
	return i
}

// Thêm Route mới vào Radix Tree
func (rt *RadixTree) Insert(path string, handler string) {
	node := rt.root
	search := path

	for {
		if len(search) == 0 {
			node.handler = handler
			return
		}

		// Tìm xem có nhánh con nào bắt đầu bằng ký tự đầu tiên của 'search' không
		var matchChild *RadixNode
		for _, child := range node.children {
			if child.path[0] == search[0] {
				matchChild = child
				break
			}
		}

		// Nếu không có nhánh nào khớp, tạo thẳng một Node mới chứa toàn bộ phần còn lại
		if matchChild == nil {
			newNode := &RadixNode{
				path:    search,
				handler: handler,
			}
			node.children = append(node.children, newNode)
			return
		}

		// Tìm tiền tố chung giữa 'search' và đường dẫn của nhánh con
		commonPrefixLen := longestCommonPrefix(search, matchChild.path)

		// 1. Nếu tiền tố chung ngắn hơn path của matchChild -> Bắt buộc phải TÁCH (Split) Node
		if commonPrefixLen < len(matchChild.path) {
			// Phần bị tách rời (đẩy xuống làm con)
			splitNode := &RadixNode{
				path:     matchChild.path[commonPrefixLen:],
				handler:  matchChild.handler,
				children: matchChild.children, // Kế thừa toàn bộ con cũ
			}

			// Cập nhật lại Node hiện tại
			matchChild.path = matchChild.path[:commonPrefixLen]
			matchChild.children = []*RadixNode{splitNode}
			matchChild.handler = "" // Nơi bị tách không còn là điểm kết thúc cũ
		}

		// 2. Cắt bỏ phần đã khớp ra khỏi 'search', chuẩn bị cho vòng lặp tiếp theo đi xuống sâu hơn
		if commonPrefixLen < len(search) {
			search = search[commonPrefixLen:]
			node = matchChild
		} else {
			// Khớp hoàn toàn, cập nhật Handler tại đây
			matchChild.handler = handler
			return
		}
	}
}

// Tìm kiếm Route
func (rt *RadixTree) Search(path string) string {
	node := rt.root
	search := path

	for len(search) > 0 {
		var matchChild *RadixNode
		for _, child := range node.children {
			if strings.HasPrefix(search, child.path) {
				matchChild = child
				break
			}
		}

		if matchChild == nil {
			return "404 Not Found"
		}

		search = search[len(matchChild.path):]
		node = matchChild
	}

	if node.handler != "" {
		return node.handler
	}
	return "404 Not Found"
}

func main() {
	router := NewRadixTree()
	
	// Khai báo các Routes
	router.Insert("/api/v1/users", "UserController@Index")
	router.Insert("/api/v1/users/active", "UserController@Active")
	router.Insert("/api/v1/posts", "PostController@Index")

	// Truy vấn thử nghiệm
	fmt.Println("GET /api/v1/users ->", router.Search("/api/v1/users"))
	fmt.Println("GET /api/v1/users/active ->", router.Search("/api/v1/users/active"))
	fmt.Println("GET /api/v1/posts ->", router.Search("/api/v1/posts"))
	fmt.Println("GET /api/v1/comments ->", router.Search("/api/v1/comments")) // Không tồn tại
}

4. Phân tích Hiệu năng và Ứng dụng Thực tế

• Thời gian Truy vấn (Routing Time): $O(K)$ (với $K$ là độ dài chuỗi URL). Việc định tuyến không tốn một chút RAM cấp phát (Zero Memory Allocation) nào và chạy hoàn toàn trên CPU Cache. Framework Gin của Golang nổi tiếng có thể định tuyến hàng vạn request mỗi giây mà không sinh ra Garbage Collection dư thừa.

• Không gian (Space): Nhỏ hơn Standard Trie rất nhiều lần nhờ nén các đường đi liên tục, cho phép load hàng nghìn endpoint lên RAM một cách gọn nhẹ.

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

Bên cạnh HTTP Router (như Gin, Echo, Fiber trong Golang), Radix Tree còn là trái tim của các hệ thống mạng quan trọng:

• IP Routing (Tra cứu Bảng định tuyến): Các Router phần cứng của Cisco hoặc Juniper sử dụng một biến thể gọi là Patricia Trie để tìm kiếm Longest Prefix Match (Tiền tố chung dài nhất) cho các dải địa chỉ IP (CIDR), giúp chuyển tiếp gói tin (Packet Forwarding) ở tốc độ hàng Terabits/s.

• Hệ thống Cache & Key-Value Stores: Bất kỳ nơi nào có Khóa (Key) là chuỗi và có nhiều tiền tố chung giống nhau, Radix Tree luôn là một giải pháp tối ưu RAM và tốc độ đáng cân nhắc so với Hash Map thông thường.