proto.lib

B-tree Page Split và Merge

Insert vào leaf B-tree đầy gây page split, đẩy separator key lên node cha; delete có thể gộp các trang thưa để giữ cây cân bằng.

DatabasesNâng cao2026-07-10
B-tree Page Split và Merge

Tags

#b-tree#page-split#index-structure#tree-balance#storage-engine

Tài liệu tham khảo

Mở rộng

Animation gốc là một file HTML tự chứa, có thể nhúng lại ở bất kỳ trang nào khác. Mở file gốc

Liên quan

DatabasesTrung bình

UUIDv4 vs UUIDv7 làm khoá chính

UUIDv4 sinh ngẫu nhiên hoàn toàn nên insert rải đều khắp B-tree, mỗi insert bẩn một trang khác nhau gây page split, cache miss và WAL amplification; UUIDv7 nhúng timestamp ở phần đầu nên các giá trị mới luôn tăng dần, insert dồn vào trang tận cùng bên phải như bigint sequence.

#uuid#primary-key#b-tree#page-split
DatabasesNâng cao

B-tree vs LSM-tree - Storage Engine

So sánh B-tree (cập nhật tại chỗ, tối ưu đọc) và LSM-tree (ghi vào memtable rồi flush SSTable, tối ưu ghi) cùng đánh đổi read/write amplification.

#b-tree#lsm-tree#storage-engine#sstable
DatabasesNâng cao

Collation và index phân biệt hoa/thường

Thứ tự sắp xếp và so sánh bằng phụ thuộc vào collation: đổi phiên bản collation của hệ điều hành/ICU có thể âm thầm làm hỏng thứ tự B-tree đã build (cần REINDEX sau khi nâng cấp glibc/ICU); LOWER(col) = LOWER(x) không dùng được index thường vì phải tính hàm trước, cần expression index hoặc kiểu citext; cùng một chuỗi có thể bằng nhau ở collation này nhưng khác ở collation khác.

#collation#citext#index#case-insensitive