App: index DB với B-tree, hash và Bloom

Giới thiệu

Bài này xây mục lục cho database mini. Tìm 1 dòng thì dùng hash, tìm 1 đoạn thì dùng cây.

Kiến thức cần nhớ

B-tree cho range query

• B-tree giữ key có thứ tự, lá nối nhau thành chuỗi.
• Insert đầy nút thì split lan lên trên.
• Range scan tìm lá đầu rồi quét ngang tới hết khoảng.
• Fanout lớn giữ cây rất thấp: fanout 100 thì 3 tầng đã chứa cỡ 1 triệu khóa, 4 tầng cỡ 100 triệu.

Hash cho point lookup

• Hash ánh xạ key tới offset bản ghi trong $O(1)$.
• Nhanh nhất cho hỏi bằng như tìm mã đơn hàng.
• Không phục vụ được hỏi khoảng vì mất thứ tự.
• Ví dụ đời thường: tra từ điển bằng số trang đánh dấu sẵn.

Bloom chặn key vắng

• Bloom nhớ toàn bộ key đã có.
• Key vắng bị chặn trước khi chạm index đắt.
• Phủ định là chắc chắn vắng, khẳng định mới cần verify.
• Planner: Bloom trước, hash cho bằng, B-tree cho khoảng.

Ví dụ

• Input: point query 50 nghìn key. Output: đúng 100% value so với quét file.
• Giải thích: hash trỏ đúng offset nên đọc đúng bản ghi.
• Input: range 1000 key liên tiếp. Output: trả đủ có thứ tự, hash bó tay.
• Giải thích: chỉ B-tree giữ thứ tự để quét đoạn.

💻 Bài tập

Ngôn ngữ: C++17. Dùng Bloom ngày 30, hash map ngày 38. Nộp vào day-145-index/.

Bài 1: B+ tree trong bộ nhớ

template <class K, class V, int ORDER = 32>
class BPlusTree {
 public:
  void insert(const K &k, const V &v);          // khóa trùng thì ghi đè
  std::optional<V> find(const K &k) const;
  bool erase(const K &k);                        // mượn hoặc gộp nút khi thiếu
  std::vector<std::pair<K, V>> range(const K &lo, const K &hi) const;   // lá nối nhau
  int height() const;
  bool check() const;   // lá cùng độ sâu, khóa có thứ tự, số khóa mỗi nút đúng giới hạn
};

insert 1..10^6 -> height không quá 5 với ORDER = 32; check = true
range(100, 200) -> 101 cặp theo thứ tự
erase mọi số chẵn -> check = true, find(2) = nullopt

Test ngẫu nhiên so với std::map sau 10^5 thao tác trộn.

Bài 2: Ba loại index trên 1 bảng

Bảng orders(id, customer_id, created_at, amount) 10^6 dòng lưu trong file nhị phân, mỗi dòng cố định 32 byte.

truy_vấn                 quét_toàn_bảng(ms)   có_index(ms)   số_dòng_đọc
id = 123456              ...
created_at trong 1 ngày  ...
customer_id vắng mặt     ...

Bài 3: B+ tree trên đĩa (nâng cao)

1. Mỗi nút là 1 trang 4096 byte trong file. Đọc ghi trang bằng pread/pwrite.
2. Thêm buffer pool LRU 256 trang. Đếm số lần đọc đĩa thật.
3. So số lần đọc đĩa cho 10.000 truy vấn điểm với buffer pool 0, 64, 256, 1024 trang.
4. Đóng chương trình, mở lại: dữ liệu vẫn còn, check() đúng.

✅ Tiêu chí hoàn thành

• B+ tree pass test ngẫu nhiên so với std::map.
• Bảng 3 truy vấn có và không có index.
• Bản trên đĩa mở lại vẫn đúng.
• Bảng số lần đọc đĩa theo kích thước buffer pool.

❓ Câu hỏi ôn tập

• B-tree phục vụ range query bằng cách nào?
• Hash nhanh cho point nhưng bó tay với gì?
• Bloom chặn key vắng trước index để làm gì?
• Planner chọn index theo loại query ra sao?

🌕 Bạn đã hoàn thành ngày 145. Làm hết bài tập phía trên rồi sang ngày tiếp theo.