Bảng to gấp 10.000 lần mà tìm một hàng vẫn đọc 6-7 trang: phép màu nông của B-tree
Bảng to gấp 10.000 lần (1k lên 10 triệu hàng) mà cây chỉ mục chỉ sâu thêm một tầng (2 lên 3), tìm một hàng vẫn đọc 6-7 trang. Tôi tưởng bảng gấp 100 lần thì tìm phải chậm hẳn — đo ra đường phẳng. Vì fanout ~360, chi phí tra cứu tăng theo log cơ số vài trăm, gần như đứng yên. Cỡ dữ liệu và chi phí tra cứu là hai thứ khác hẳn.