Elasticsearch Bài học 8: Inverted Index là gì mà giúp Elasticsearch tìm kiếm full-text nhanh đến vậy?

Ở Bài 7, chúng ta đã chia nhỏ dữ liệu thành các Shard để giải quyết bài toán dung lượng phần cứng. Nhưng điều làm nên thương hiệu "vua tìm kiếm" của Elasticsearch không nằm ở phần cứng, mà nằm ở một cấu trúc dữ liệu kinh điển bên trong lõi Apache Lucene: Inverted Index (Chỉ mục đảo ngược).

Nếu bạn đã từng mệt mỏi với việc tối ưu câu query LIKE '%keyword%' trên MySQL, bài học này sẽ giải thích chính xác tại sao Elasticsearch lại giải quyết được bài toán đó chỉ trong vài mili-giây.

1. Vấn đề của B-Tree Index trong MySQL

Các cơ sở dữ liệu quan hệ (RDBMS) như MySQL hay PostgreSQL mặc định sử dụng cấu trúc B-Tree (Balanced Tree) để đánh index. B-Tree hoạt động giống như danh bạ điện thoại: Dữ liệu được sắp xếp theo thứ tự bảng chữ cái (từ trái sang phải).

Khi bạn tìm kiếm chính xác (Exact match) hoặc tìm theo tiền tố (LIKE 'Sữa%'), B-Tree lướt qua các node và tìm thấy kết quả ở mức $O(\log n)$. Rất nhanh.

Nhưng khi người dùng gõ vào ô tìm kiếm E-commerce từ khóa nằm giữa câu (LIKE '%rửa mặt%'), B-Tree hoàn toàn vô dụng. Vì nó không biết từ "rửa" bắt đầu ở đâu trong chuỗi, MySQL buộc phải thực hiện Full Table Scan (quét từng dòng một trong hàng triệu dòng). Kết quả là CPU server bị treo, RAM bị ngốn sạch và API request bị timeout.

2. Inverted Index là gì?

Inverted Index (Chỉ mục đảo ngược) hoạt động giống hệt phần "Mục lục tra cứu" (Index) ở những trang cuối của một cuốn sách bách khoa toàn thư.

Thay vì liệt kê Trang 1 có chữ gì, Trang 2 có chữ gì (đây gọi là Forward Index), Mục lục sẽ liệt kê các Từ khóa (Terms) và ghi chú lại Danh sách các trang (Document IDs) chứa từ khóa đó.

Tại sao gọi là "đảo ngược"? Vì nó đảo ngược quy trình mapping: Thay vì map Document -> Text, nó map Text -> Document.

3. Quá trình "xây" Inverted Index diễn ra như thế nào?

Hãy lấy ví dụ hệ thống của bạn có 3 Document chứa tên sản phẩm:

• Doc 1: "sữa rửa mặt da mụn"

• Doc 2: "kem trị mụn cho da dầu"

• Doc 3: "sữa rửa mặt cetaphil"

Khi bạn POST 3 Document này vào Elasticsearch, dữ liệu không được ghi vào ổ cứng ngay. Nó sẽ đi qua một bộ phân tích văn bản (Analyzer) với 2 bước cốt lõi:

Bước 1: Tokenization (Tách từ)

Hệ thống sẽ chặt các câu dài thành các từ khóa đơn lẻ (Token), đồng thời chuyển hết về chữ thường (lowercase) và loại bỏ các ký tự đặc biệt.

Bước 2: Xây dựng bảng Index

Elasticsearch tổng hợp các token lại, sắp xếp chúng theo bảng chữ cái và tạo ra cấu trúc Inverted Index như sau:

_Bảng này được tối ưu cực kỳ nhỏ gọn để có thể load thẳng lên RAM (Heap Memory)._

4. Cỗ máy tìm kiếm hoạt động ra sao?

Bây giờ, một khách hàng vào thanh tìm kiếm của Hasaki và gõ: "sữa mụn".

1. Phân tích query: Cụm từ tìm kiếm cũng được Analyzer tách thành 2 token: ["sữa", "mụn"].

2. Tra cứu (Lookup): Elasticsearch quét trong bảng Inverted Index (nhờ cấu trúc băm hoặc cây nhị phân, việc này chỉ mất $O(1)$ hoặc $O(\log n)$).

   • Từ "sữa" -> trỏ tới [1, 3]

   • Từ "mụn" -> trỏ tới [1, 2]

3. Xử lý tập hợp (Set Operations):

   • Nếu khách hàng muốn tìm chuỗi chứa CẢ 2 từ (Toán tử AND), Elasticsearch thực hiện phép Giao (Intersection) hai mảng: [1, 3] ∩ [1, 2] = [1]. Kết quả trả về Doc 1.

   • Nếu khách hàng muốn tìm chuỗi chứa 1 TRONG 2 từ (Toán tử OR), Elasticsearch thực hiện phép Hợp (Union): [1, 3] ∪ [1, 2] = [1, 2, 3]. Kết quả trả về cả 3 Doc.

Nhờ áp dụng toán học trên các Bitset (chuỗi bit 0 và 1 thể hiện ID), Elasticsearch có thể tính toán hàng triệu tập hợp Giao/Hợp này chỉ trong chưa tới chục mili-giây. Không có bất kỳ phép "Full table scan" nào diễn ra ở đây cả.

5. Sự đánh đổi (Trade-offs)

Không có cấu trúc dữ liệu nào hoàn hảo. Để đổi lấy tốc độ truy vấn ánh sáng, Inverted Index yêu cầu hai sự hy sinh:

1. Đánh đổi bộ nhớ và ổ đĩa: Bạn sẽ tốn thêm dung lượng để lưu trữ cấu trúc Inverted Index, ngoài dung lượng lưu JSON gốc.

2. Tính Bất biến (Immutability): Để hỗ trợ đọc siêu nhanh và cho phép các luồng (Thread) truy cập đồng thời mà không bị kẹt Lock (Pessimistic/Optimistic locking), Inverted Index sau khi được ghi xuống ổ cứng sẽ không bao giờ có thể bị thay đổi.

Điều này dẫn đến một vấn đề lớn: Nếu Inverted Index không thể sửa, vậy làm sao Elasticsearch có thể Update hay Delete dữ liệu? Hệ thống làm cách nào để cập nhật dữ liệu mới vào bảng Index mà không cần build lại toàn bộ từ đầu?