3.3 Postings và lưu trữ: index nằm ở đâu, tốn bao nhiêu

Inverted index gồm hai phần, và chúng có tính chất rất khác nhau:

Phần	Chứa gì	Kích thước	Ở đâu
Dictionary (term dictionary)	mỗi term một lần, kèm df và con trỏ tới postings	nhỏ — theo số term	thường nằm hết trong RAM
Postings	với mỗi term: danh sách doc id, tf, (và vị trí)	lớn — theo tổng số lần xuất hiện	trên đĩa, đọc theo khối

Một posting chứa gì

term "mật"  ->  [ (d1, tf=1, pos=[1]), (d2, tf=2, pos=[2,5]) ]
                   ^      ^                 ^
                doc id   để tính điểm     để khớp cụm từ (3.5)

Ba mức, ba giá:

Mức	Trả lời được	Chi phí tương đối
chỉ doc id	“có chứa không” (boolean)	1×
+ tf, độ dài doc	ranking BM25	~1.3×
+ vị trí	cụm từ, khoảng cách gần	~2–4×

Vị trí là phần đắt nhất của index. Nếu sản phẩm không dùng truy vấn cụm từ, tắt nó là khoản tiết kiệm lớn nhất và dễ nhất.

Đọc thêm

• [VI] Bí mật tốc độ của Elasticsearch: giải phẫu Inverted Index — Viblo — cái giá của inverted index ở khâu ghi, bằng tiếng Việt
• [EN] Elasticsearch from the bottom up — Elastic — postings thật trong Lucene: skip list, doc values

Nén: tại sao index nhỏ hơn dữ liệu gốc

Postings là dãy số nguyên tăng dần → nén rất tốt qua hai bước:

1. Lưu khoảng cách (delta / gap), không lưu số tuyệt đối.

doc id:  1024, 1030, 1031, 1090, 1092
gap:     1024,    6,    1,   59,    2     ← số nhỏ hơn nhiều

2. Mã hoá số nhỏ bằng ít byte — VByte (7 bit dữ liệu + 1 bit tiếp tục), hoặc theo khối như PForDelta/FOR: chia 128 doc id một khối, tìm số bit tối đa cần trong khối, đóng gói cả khối bằng đúng số bit đó. Lucene dùng cách này.

Hệ quả thực tế: term càng phổ biến (gap càng nhỏ) thì nén càng tốt — nghịch với trực giác “term phổ biến tốn nhiều chỗ”.

Dictionary cũng nén được: FST (finite state transducer) chia sẻ tiền tố và hậu tố chung giữa các term. Đây không chỉ là chuyện tiết kiệm — FST là cấu trúc làm cho 3.6 prefix/wildcard và 3.9 fuzzy nhanh khả thi.

Đọc thêm

• [EN] IR Book ch.5 — Index compression — gap encoding, variable byte, gamma code — nén postings
• [EN] IR Book ch.4 — Index construction — dựng index khi dữ liệu không vừa RAM

Ước lượng bằng tay

Cần một con số trước khi chọn hạ tầng. Giả sử:

1.000.000 chunk × 200 term/chunk = 200.000.000 lần xuất hiện

Cấu hình	Byte/posting (sau nén, ước lượng)	Tổng
doc id + tf	~1,5–2 B	~300–400 MB
+ vị trí	~4–6 B	~0,8–1,2 GB

So sánh với vector đặc cùng corpus: 1.000.000 × 768 chiều × 4 byte = 3 GB chưa tính bản sao của cấu trúc ANN. Đó là một lý do rất thực tế để không bỏ lexical: nó rẻ hơn gần một bậc độ lớn (Tầng 5 có toán bộ nhớ đầy đủ).

Mọi số ở trên là ước lượng bậc độ lớn để lập kế hoạch, không phải số đo trên corpus của cẩm nang. Cách duy nhất để biết con số của bạn: index thử 1% dữ liệu rồi nhân lên.