Các cấu trúc như trie, radix tree và rax tree đều là những biến thể của cây tiền tố (prefix tree), được thiết kế để tối ưu hóa hiệu suất truy vấn và tiết kiệm bộ nhớ theo từng giai đoạn phát triển.

Trie truyền thống

Mỗi nút trong trie chỉ lưu một ký tự duy nhất, toàn bộ khóa được tạo thành bởi chuỗi đường đi từ gốc đến lá. Độ phức tạp tìm kiếm là O(k) — với k là độ dài khóa. Tuy nhiên, nhược điểm lớn là lãng phí bộ nhớ do tồn tại nhiều nút đơn nhánh.

        (gốc)
       /     \
      a       b
     /         \
    p           a
   / \           \
  p   p           n
 /     \           \
l       l           a
e       e           n
                     a

Ví dụ trên cho thấy "app" và "apple" cùng chia sẻ tiền tố "app", nhưng vẫn phải tách nhánh tại ký tự 'p', gây dư thừa không cần thiết.

Radix Tree – Cây tiền tố nén

Radix tree cải tiến bằng cách gộp các nhánh liên tiếp thành một nút chứa chuỗi con, thay vì từng ký tự riêng lẻ. Điều này giúp giảm đáng kể số lượng nút và tiết kiệm bộ nhớ.

        (gốc)
       /     \
     app     banana
    /   \
   le    (rỗng)

Bây giờ, "app" trở thành một nút duy nhất, còn "le" là phần mở rộng treo bên dưới. Cấu trúc này đặc biệt hiệu quả với dữ liệu có tiền tố chung dài, ví dụ như định tuyến URL hoặc hệ thống phân cấp ID.

Rax Tree – Cây radix thích ứng trong Redis

Rax tree nâng cấp thêm bằng cơ chế tự động chọn loại nút phù hợp dựa trên mật độ con, nhằm cân bằng giữa tốc độ và bộ nhớ:

• Nút đơn ký tự: Dùng khi chỉ có 0 hoặc 1 con — giống trie truyền thống.
• Nút đa ký tự: Gộp chuỗi liên tiếp nếu chỉ có một nhánh con.
• Nút mảng: Khi số con ≤ 16, dùng mảng cố định để truy cập O(1).
• Nút băm: Khi số con > 16, chuyển sang bảng băm để tránh lãng phí bộ nhớ.

Ví dụ thực tế trong Redis Stream: ID dạng 1630000000000-1 được lưu trữ hiệu quả nhờ tính chất có thứ tự và tiền tố lặp lại. Thao tác XRANGE tận dụng cấu trúc cây để duyệt phạm vi với độ phức tạp O(log n).

Chuyển đổi linh hoạt giữa các loại nút

Khi thêm hoặc xóa dữ liệu, rax tree tự động nâng cấp hoặc hạ cấp loại nút:

• Thêm khóa mới khiến số con vượt ngưỡng → chuyển từ mảng sang băm.
• Xóa khiến số con giảm → hạ cấp từ băm về mảng, rồi về nút gộp.

Việc chuyển đổi diễn ra "lười biếng" — chỉ khi sự thay đổi đủ lớn — nhằm tránh ảnh hưởng hiệu năng thời gian thực.

Giao diện thống nhất

Dù bên trong sử dụng nhiều loại nút khác nhau, API như raxInsert hay raxFind vẫn giữ nguyên, giúp người dùng không cần quan tâm đến chi tiết cài đặt.

Ứng dụng trong Redis Stream

Khi chèn ID 1630000000000-1:

1. Bắt đầu bằng nút đơn ký tự '1'.
2. Thêm '6', '3'... → gộp thành nút "163".
3. Tiếp tục chèn các phần sau → có thể chuyển sang nút mảng hoặc băm tùy mật độ.

Truy vấn theo phạm vi (XRANGE) tận dụng thứ tự từ điển của các ID để duyệt tuần tự qua các nút lá.

Các biến thể khác trong thực tế