1.6 Inverted index — dựng bằng tay
Đây là cấu trúc làm cho search nhanh. Nó lật ngược quan hệ thông thường.
Xuôi (cách bạn nghĩ tự nhiên): tài liệu → danh sách từ trong nó. Ngược (inverted): từ → danh sách tài liệu chứa nó.
Ba tài liệu tí hon:
| id | nội dung | số từ |
|---|---|---|
| d1 | đổi mật khẩu trong phần cài đặt | 7 |
| d2 | khôi phục mật khẩu khi quên mật khẩu | 8 |
| d3 | bật xác thực hai lớp | 5 |
Inverted index (mỗi từ → các tài liệu chứa nó, kèm số lần xuất hiện):
| từ | postings (tài liệu : số lần) |
|---|---|
| mật | d1:1, d2:2 |
| khẩu | d1:1, d2:2 |
| quên | d2:1 |
| đổi | d1:1 |
| khôi | d2:1 |
| xác | d3:1 |
| … | … |
Giờ truy vấn quên mật khẩu. Ta chỉ cần đọc 3 dòng trong bảng trên, lấy hợp
của chúng: {d1, d2}. d3 không bao giờ được chạm tới.
Đó là toàn bộ phép màu: với một triệu tài liệu mà truy vấn có 3 từ, bạn chỉ chạm vào các tài liệu thực sự chứa ít nhất một trong ba từ đó. Đây là lợi thế cấu trúc mà vector search không có — vector search về nguyên tắc phải so sánh với mọi vector (và đó là lý do phải có ANN, Tầng 5).
Đi sâu hơn. Bảng trên là phiên bản trên giấy. Ở mức thật: một posting chứa gì, nén thế nào, giao hai danh sách ra sao — 3.2 Boolean retrieval và 3.3 Postings và lưu trữ.