Inverted Index
Inverted Index (Chỉ mục ngược) là cấu trúc dữ liệu cốt lõi giúp Elasticsearch (và nền tảng bên dưới là Apache Lucene) thực hiện việc tìm kiếm Full-text (toàn văn) với tốc độ cực nhanh.
Hiểu đơn giản, nếu Forward Index là mục lục ở đầu sách (Trang -> Nội dung), thì Inverted Index chính là phần Index ở cuối sách (Từ khóa -> Những trang chứa từ khóa đó).
Dưới đây là phân tích sâu về cách nó hoạt động, cấu trúc và lý do tại sao nó hiệu quả.
1. Cơ chế hoạt động (Ví dụ minh họa)
Giả sử bạn có 3 văn bản (Documents) được nạp vào Elasticsearch:
Doc 1: "Google engineer"
Doc 2: "Backend engineer"
Doc 3: "Google backend"
Khi dữ liệu được đánh chỉ mục (indexing), Elasticsearch sẽ thực hiện quá trình Analysis (Tokenization, Lowercasing, Stop words filter, etc.). Giả sử chúng ta chỉ tách từ và chuyển về chữ thường, Inverted Index sẽ trông như sau:
backend
2
[2, 3]
engineer
2
[1, 2]
2
[1, 3]
Khi bạn tìm kiếm: "Google"
ES tra trong cột Term: thấy "google".
Lấy danh sách trong Postings List: trả về Doc 1 và Doc 3. -> Tốc độ tìm kiếm là rất nhanh vì nó không phải quét qua toàn bộ văn bản (Scan), mà chỉ tra cứu từ khóa.
2. Cấu trúc chuyên sâu (Dành cho Senior Engineer)
Thực tế, Inverted Index trong Lucene phức tạp hơn bảng trên để tối ưu hóa I/O và Memory. Nó bao gồm 3 phần chính:
A. Term Dictionary (Từ điển thuật ngữ)
Đây là danh sách các từ (terms) đã được sắp xếp (sorted). Vì nó được sắp xếp, ta có thể dùng thuật toán tìm kiếm nhị phân (Binary Search).
Nó chứa thông tin meta như tần suất xuất hiện (dùng để tính điểm Relevance scoring - BM25).
B. Term Index (Chỉ mục thuật ngữ)
Nếu Term Dictionary quá lớn để lưu trên RAM, việc tìm kiếm trên đĩa sẽ chậm. Term Index giống như một cái cây B-Tree (cụ thể là Prefix Tree / FST - Finite State Transducer), nó nằm hoàn toàn trên RAM.
Nó giúp tìm nhanh vị trí (offset) của một từ trong
Term Dictionarynằm trên đĩa cứng.Quy trình: Term Index (RAM) -> Term Dictionary (Disk/Page Cache) -> Postings List (Disk).
C. Postings List
Đây là danh sách các Document ID chứa term đó. Ngoài Doc ID, nó còn lưu:
Positions: Vị trí của từ trong câu (dùng cho phrase search - tìm kiếm cụm từ chính xác).
Offsets: Vị trí bắt đầu/kết thúc ký tự (dùng cho highlighting).
3. Tại sao Inverted Index lại nhanh và nhẹ?
Là một Senior Backend Engineer, bạn sẽ quan tâm đến cách nó tối ưu hóa lưu trữ:
Immutability (Bất biến):
Một khi Inverted Index (trong một Segment) đã được ghi xuống đĩa, nó không bao giờ thay đổi.
Lợi ích: Không cần khóa (lock) khi đọc (tăng concurrency), tận dụng tối đa File System Cache của OS.
Hệ quả: Khi bạn Update một document, ES thực chất là đánh dấu bản ghi cũ là "deleted" và tạo một bản ghi mới trong segment mới. (Đây là lý do cần định kỳ Force Merge để dọn dẹp).
Compression (Nén dữ liệu - Frame of Reference & Roaring Bitmaps):
Postings List thường chứa các số nguyên (Doc IDs) tăng dần:
[100, 105, 108].ES không lưu nguyên số, mà lưu Delta (khoảng cách):
[100, 5, 3]. Số nhỏ hơn tốn ít bit hơn để lưu trữ (Frame of Reference encoding).Với các tập dữ liệu dày đặc, nó sử dụng Roaring Bitmaps để thực hiện các phép toán tập hợp (Intersection/Union) cực nhanh ở cấp độ bitwise.
4. Sự khác biệt: Inverted Index vs. Stored Fields (Source)
Khi bạn GET /index/_doc/1, bạn thấy toàn bộ JSON. Đó không phải là Inverted Index.
_source: Là dữ liệu gốc, được lưu trữ theo dòng (row-oriented) để lấy ra hiển thị.
Inverted Index: Là cấu trúc tách rời, chỉ dùng để search (tìm kiếm xem doc nào khớp).
Lưu ý quan trọng: Nếu bạn tắt Inverted Index cho một trường (gán
index: falsetrong Mapping), bạn vẫn có thể lấy dữ liệu đó về (trong_source), nhưng bạn không thể query (filter/match) trên trường đó được nữa.
Last updated