Đã đăng vào khoảng 8 giờ trước 14 phút đọc

HNSW và B-tree/B+ tree: Cùng là index, nhưng giải quyết hai bài toán khác nhau

Khi nói đến “tăng tốc tìm kiếm dữ liệu”, người mới tìm hiểu vector database hoặc AI search rất dễ đặt HNSW cạnh những cấu trúc index quen thuộc như B-tree và B+ tree. Cả hai đều giúp hệ thống tránh quét tuần tự toàn bộ dữ liệu, nhưng chúng giải quyết những loại truy vấn khác nhau.

B-tree/B+ tree khai thác một quan hệ thứ tự: bằng, nhỏ hơn, lớn hơn, nằm trong một khoảng hoặc sắp xếp theo khóa.
HNSW khai thác khoảng cách giữa các vector: tìm những điểm gần vector truy vấn nhất theo cosine, L2 hoặc inner product.

Vì vậy, câu hỏi quan trọng không phải là “index nào nhanh hơn?”, mà là chúng ta đang cần tăng tốc loại truy vấn nào?

Bài viết này không benchmark trực tiếp HNSW với B-tree/B+ tree, bởi chúng không xử lý cùng một loại truy vấn. Việc đặt hai cấu trúc cạnh nhau nhằm làm rõ vì sao cả hai đều được gọi là index, chúng dựa trên quan hệ dữ liệu nào và cách chúng có thể bổ sung cho nhau trong một hệ thống tìm kiếm hiện đại.

1. Vì sao hai cấu trúc dễ bị nhầm lẫn?

Cả B-tree/B+ tree và HNSW đều được gọi là index. Chúng đều đánh đổi thêm dung lượng lưu trữ và chi phí xây dựng/cập nhật để giảm thời gian truy vấn. Tuy nhiên, chúng dựa trên hai quan hệ toán học khác nhau: B-tree/B+ tree dựa trên quan hệ thứ tự giữa các khóa, còn HNSW dựa trên hàm khoảng cách hoặc độ tương đồng giữa các vector.

Với B-tree/B+ tree, các khóa nằm trên một trật tự tuyến tính. Chẳng hạn, 10 < 20 < 30, hoặc ngày 2026-01-01 đứng trước 2026-02-01. Nhờ trật tự đó, cây có thể nhanh chóng loại bỏ những nhánh không thể chứa kết quả.

Với HNSW, mỗi đối tượng được biểu diễn bằng một vector nhiều chiều. Hai văn bản có thể dùng từ khác nhau nhưng vẫn có vector gần nhau nếu embedding model đánh giá chúng có ý nghĩa tương tự. Truy vấn lúc này không phải “khóa có bằng X không?” mà là “đâu là k vector có khoảng cách nhỏ nhất tới X?”.

2. B-tree và B+ tree trong cơ sở dữ liệu

B-tree khác B+ tree như thế nào?

Cả hai đều là cây tìm kiếm cân bằng có độ phân nhánh lớn. Một node thường tương ứng với một page trên đĩa hoặc trong bộ nhớ, vì vậy việc chứa nhiều khóa trong mỗi node giúp cây có chiều cao nhỏ và giảm số page phải đọc.

B-tree được Rudolf Bayer và Edward McCreight giới thiệu trong bài báo Organization and Maintenance of Large Ordered Indexes năm 1972. Bài báo mô tả cách tổ chức các page của một index động để thao tác tìm kiếm, chèn và xóa tăng theo logarithm của kích thước index. Một tài liệu tổng quan kinh điển khác là The Ubiquitous B-Tree của Douglas Comer, trong đó tác giả khảo sát họ B-tree và thảo luận riêng biến thể B+ tree.

Trong mô hình kinh điển:

B-tree có thể lưu bản ghi hoặc con trỏ tới bản ghi ở cả node nội bộ và node lá.
B+ tree chỉ lưu dữ liệu hoặc con trỏ tới dữ liệu ở các node lá; node nội bộ chủ yếu chứa khóa phân cách để định tuyến.
Các lá của B+ tree thường được liên kết với nhau, giúp quét một khoảng khóa liên tiếp hiệu quả.

Trong tài liệu sản phẩm, “B-tree” đôi khi được dùng để chỉ cả họ cấu trúc này. PostgreSQL gọi index mặc định của mình là B-tree; MySQL cũng mô tả các index InnoDB thông thường là B-tree và lưu index record ở các leaf page. Vì vậy, không nên mặc định rằng mọi câu lệnh CREATE INDEX trong mọi hệ quản trị đều tạo ra đúng một B+ tree.

B-tree/B+ tree giải quyết tốt truy vấn nào?

Các truy vấn điển hình gồm:

-- Tìm chính xác theo khóa
SELECT * FROM products WHERE product_id = 123;

-- Tìm theo khoảng
SELECT *
FROM products
WHERE price BETWEEN 100000 AND 500000
ORDER BY price;

Với một cây cân bằng, point lookup thường có độ phức tạp O(log n). Range query thường có chi phí O(log n + k): O(log n) để tìm điểm bắt đầu và O(k) để đọc k kết quả trong khoảng.

B-tree còn có thể hỗ trợ ORDER BY. Nếu thứ tự của index phù hợp với truy vấn, database có thể đọc kết quả theo thứ tự sẵn có thay vì sắp xếp lại toàn bộ tập dữ liệu.

Pseudocode minh họa point lookup và range scan

Đoạn mã sau chỉ minh họa cách tìm kiếm trên một cây đã được xây dựng. Nó cố ý không cài đặt insert, delete, split, merge hoặc cân bằng lại cây vì một implementation đầy đủ sẽ dài hơn đáng kể.

from bisect import bisect_left, bisect_right


class BPlusTreeNode:
    def __init__(self, is_leaf=False):
        self.is_leaf = is_leaf
        self.keys = []
        self.children = []  # node nội bộ: số phần tử = len(keys) + 1
        self.values = []    # node lá: minh họa trường hợp khóa duy nhất
        self.next = None    # node lá kế tiếp


class BPlusTree:
    def __init__(self, root):
        self.root = root

    def _find_leaf(self, key):
        node = self.root
        while not node.is_leaf:
            # Quy ước: khóa bằng separator được định tuyến sang nhánh phải.
            child_index = bisect_right(node.keys, key)
            node = node.children[child_index]
        return node

    def search(self, key):
        leaf = self._find_leaf(key)
        index = bisect_left(leaf.keys, key)

        if index < len(leaf.keys) and leaf.keys[index] == key:
            return leaf.values[index]
        return None

    def range_query(self, start, end):
        """Trả về các cặp (key, value) có start <= key <= end."""
        leaf = self._find_leaf(start)
        index = bisect_left(leaf.keys, start)
        result = []

        while leaf is not None:
            while index < len(leaf.keys):
                key = leaf.keys[index]
                if key > end:
                    return result
                result.append((key, leaf.values[index]))
                index += 1

            leaf = leaf.next
            index = 0

        return result

Điểm đáng chú ý là range_query() không bắt đầu từ lá trái nhất. Nó dùng cây để tìm thẳng tới lá chứa start, rồi mới đi qua các lá kế tiếp.

3. HNSW và bài toán tìm kiếm vector

HNSW là viết tắt của Hierarchical Navigable Small World. Cấu trúc này tổ chức các vector thành một đồ thị nhiều lớp:

Lớp trên thưa, chứa ít điểm và tạo ra những bước “nhảy xa”.
Càng xuống thấp, đồ thị càng dày và cho phép tinh chỉnh vùng tìm kiếm.
Mỗi phần tử được gán ngẫu nhiên một mức cao nhất; càng lên lớp cao thì số phần tử càng ít.

Khi truy vấn, HNSW bắt đầu từ một entry point ở lớp cao. Thuật toán di chuyển sang các đỉnh gần vector truy vấn hơn, lần lượt đi xuống các lớp và mở rộng một tập ứng viên ở lớp đáy.

HNSW là thuật toán Approximate Nearest Neighbor (ANN). Nó không đảm bảo luôn trả về đúng k láng giềng gần nhất tuyệt đối. Đổi lại, trên nhiều tập dữ liệu thực tế, nó đạt latency thấp và recall cao hơn đáng kể so với việc tính khoảng cách tới mọi vector.

Điều làm B-tree không phù hợp ở đây không đơn thuần là “vector có nhiều chiều”. Quan trọng hơn, thứ tự tuyến tính của một B-tree thông thường không bảo toàn quan hệ láng giềng theo cosine hoặc L2. Hai vector đứng gần nhau theo thứ tự từ điển chưa chắc gần nhau theo metric mà ứng dụng sử dụng.

Ví dụ với `hnswlib`

import hnswlib
import numpy as np

rng = np.random.default_rng(42)

dim = 128
num_elements = 10_000
k = 5

# Dữ liệu ngẫu nhiên chỉ dùng để minh họa API, không phải benchmark.
data = rng.random((num_elements, dim), dtype=np.float32)
ids = np.arange(num_elements)

index = hnswlib.Index(space="cosine", dim=dim)
index.init_index(
    max_elements=num_elements,
    M=16,
    ef_construction=200,
)
index.add_items(data, ids)

# ef phải >= k. Tăng ef thường tăng recall nhưng cũng tăng latency.
index.set_ef(50)

query_vector = rng.random((1, dim), dtype=np.float32)
labels, distances = index.knn_query(query_vector, k=k)

print("Các ID gần nhất:", labels[0])
print("Cosine distance:", distances[0])

Với space="cosine", giá trị trả về là cosine distance, tức 1 - cosine_similarity; số nhỏ hơn thể hiện hai vector gần nhau hơn.

Ba tham số quan trọng

M điều khiển số liên kết được tạo trong đồ thị. Giá trị lớn thường cải thiện khả năng tìm kiếm trên dữ liệu phức tạp, nhưng làm tăng bộ nhớ và chi phí xây dựng.
ef_construction điều khiển độ rộng tìm kiếm khi xây index. Giá trị lớn hơn thường tạo đồ thị tốt hơn nhưng build chậm hơn.
ef hoặc ef_search điều khiển độ rộng tập ứng viên khi truy vấn. Giá trị này phải không nhỏ hơn k; tăng nó thường cải thiện recall nhưng làm truy vấn chậm hơn.

Không có một bộ tham số tối ưu cho mọi tập dữ liệu. Chúng cần được đo trên chính embedding, metric, lượng dữ liệu và yêu cầu latency của hệ thống.

4. So sánh tổng quan

Tiêu chí	B-tree/B+ tree	HNSW
Quan hệ được khai thác	Thứ tự giữa các khóa	Khoảng cách hoặc độ tương đồng giữa vector
Truy vấn chính	Equality, range, prefix phù hợp, `ORDER BY`	Approximate k-nearest-neighbor
Cấu trúc	Cây cân bằng, độ phân nhánh lớn	Đồ thị small-world nhiều lớp
Kết quả	Chính xác theo toán tử so sánh	Xấp xỉ, có đánh đổi latency–recall
Đặc tính hiệu năng	Point lookup thường có độ phức tạp `O(log n)`	Hiệu năng phụ thuộc dữ liệu, metric và các tham số như `M`, `ef_construction`, `ef_search`
Có thể so latency trực tiếp?	Không, nếu hai bên thực hiện hai loại truy vấn khác nhau	Không, nếu hai bên thực hiện hai loại truy vấn khác nhau
Có thể so latency trực tiếp?	Không, nếu hai bên thực hiện hai loại truy vấn khác nhau	Không, nếu hai bên thực hiện hai loại truy vấn khác nhau
Range query theo khóa	Tự nhiên và hiệu quả	Không phải mục tiêu thiết kế
Chi phí chính	Dung lượng index; chi phí cập nhật khi ghi	Bộ nhớ, thời gian build, chi phí cập nhật và tuning
Chỉ số đánh giá	Latency, số page đọc, selectivity	Recall@k, latency, memory, build time
Ứng dụng	Khóa chính, ngày tháng, giá tiền, trạng thái	Semantic search, RAG, recommendation, tìm ảnh tương tự

Nếu cần lựa chọn vector index cho cùng một bài toán nearest-neighbor, HNSW nên được so sánh với FLAT, IVF, DiskANN hoặc ScaNN. Trong nhóm scalar index, B-tree/B+ tree thường được đặt cạnh hash index, bitmap index hoặc các cấu trúc phục vụ truy vấn có thứ tự khác. Vì vậy, bảng trên chỉ so sánh vai trò và nguyên lý, không phải hiệu năng giữa hai thuật toán cạnh tranh trực tiếp.

5. Khi cả hai xuất hiện trong cùng một hệ thống

Một bảng PostgreSQL dùng pgvector có thể chứa cả index metadata và index vector:

CREATE INDEX products_category_idx
ON products (category_id);

CREATE INDEX products_embedding_hnsw_idx
ON products
USING hnsw (embedding vector_cosine_ops);

Truy vấn kết hợp có thể trông như sau:

SELECT id, name, embedding <=> :query_vector AS distance
FROM products
WHERE category_id = 123
ORDER BY embedding <=> :query_vector
LIMIT 5;

Về mặt logic, truy vấn yêu cầu tìm năm sản phẩm gần vector truy vấn nhất trong một category. Tuy nhiên, không nên mặc định rằng PostgreSQL luôn dùng B-tree để tạo tập con trước rồi mới chạy HNSW trên tập đó.

Với approximate index của pgvector, filter có thể được áp dụng sau HNSW index scan. Nếu điều kiện chỉ giữ lại một tỷ lệ nhỏ bản ghi, truy vấn có thể nhận ít hơn k kết quả hoặc recall thấp. Những lựa chọn cần cân nhắc gồm:

Tăng hnsw.ef_search.
Bật iterative index scan.
Dùng partial HNSW index khi chỉ có ít giá trị metadata quan trọng.
Partition bảng khi cần tách dữ liệu thành nhiều nhóm lớn.
Với tập sau lọc rất nhỏ, dùng B-tree cho điều kiện metadata rồi exact vector search có thể phù hợp hơn.

Quyết định cuối cùng thuộc về query planner và phụ thuộc dữ liệu. Hãy dùng EXPLAIN (ANALYZE, BUFFERS) trên workload thực tế thay vì suy luận chỉ từ việc hai index cùng tồn tại.

6. Mỗi loại index đảm nhiệm vai trò gì?

Chọn B-tree/B+ tree khi cần:

Tìm bản ghi theo khóa hoặc điều kiện bằng.
Lọc theo khoảng ngày, giá tiền hoặc giá trị có thứ tự.
Tận dụng index cho ORDER BY và LIMIT.
Kết quả chính xác theo điều kiện so sánh.

Chọn HNSW khi cần:

Tìm văn bản gần nghĩa dựa trên embedding.
Tìm ảnh, sản phẩm hoặc người dùng tương tự.
Xây semantic search, RAG hoặc recommendation.
Chấp nhận kết quả xấp xỉ để đổi lấy latency thấp ở quy mô lớn.

Trong một hệ thống thực tế, hai loại index thường bổ sung cho nhau: B-tree xử lý cấu trúc và metadata; HNSW xử lý quan hệ tương đồng trong không gian vector.

7. Đánh giá HNSW như thế nào?

Một benchmark HNSW không nên chỉ báo cáo “mất bao nhiêu mili giây”. Cần tạo một baseline bằng exact search rồi đo ít nhất bốn đại lượng:

Recall@k: tỷ lệ kết quả ANN trùng với k kết quả của exact search.
Latency: nên có p50 và p95 hoặc p99, không chỉ lấy trung bình.
Kích thước index và mức dùng bộ nhớ.
Thời gian xây dựng index.

Recall@k có thể tính như sau:

recall@k = |ANN_k ∩ exact_k| / k

Sau đó thay đổi M, ef_construction và ef_search để tìm điểm cân bằng phù hợp. Một cấu hình nhanh nhưng recall thấp không thể được gọi là tốt nếu ứng dụng bỏ sót các tài liệu quan trọng; ngược lại, đẩy recall lên rất cao có thể không đáng nếu latency và bộ nhớ vượt ngân sách hệ thống.

8. Kết luận

HNSW và B-tree/B+ tree không phải hai phiên bản của cùng một kỹ thuật index. Chúng dựa trên hai loại quan hệ khác nhau:

B-tree/B+ tree khai thác thứ tự của khóa để phục vụ equality, range và ordering.
HNSW khai thác khoảng cách giữa các vector để tìm láng giềng gần nhất theo cách xấp xỉ.

Khi thiết kế hệ thống, hãy bắt đầu từ ngữ nghĩa của truy vấn, sau đó mới chọn index. Với semantic search hoặc RAG, lựa chọn thường không phải “B-tree hay HNSW”, mà là dùng B-tree cho metadata và dùng HNSW cho vector như thế nào để vẫn đạt recall và latency mong muốn.

Tài liệu tham khảo

Bayer, McCreight, Organization and Maintenance of Large Ordered Indexes, Acta Informatica, 1972 — bài báo nền tảng giới thiệu B-tree.
Douglas Comer, The Ubiquitous B-Tree, ACM Computing Surveys, 1979 — tổng quan B-tree và các biến thể, đặc biệt có B+ tree.
NIST Dictionary of Algorithms and Data Structures, B+ tree — định nghĩa tham khảo ngắn gọn về B+ tree.
Malkov, Yashunin, Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.
hnswlib: API và các distance space.
hnswlib: hướng dẫn tham số HNSW.
PostgreSQL, Index Types và Indexes and ORDER BY.
MySQL, The Physical Structure of an InnoDB Index.
pgvector, Filtering và iterative index scans.

HNSW b-tree