[Hacker News] B-trees and database indexes (2024)
Nguồn: PlanetScale Blog Tóm tắt B-tree là cấu trúc dữ liệu cân bằng tự động, được sử dụng rộng rãi để triển khai index trong database. Mỗi node của B-tree chứa keys và values: node gốc và node nội bộ dùng để dẫn đường tìm kiếm, còn node lá chứa con trỏ đến dữ liệu thực. Tính chất tự cân bằng đảm bảo độ phức tạp tìm kiếm luôn là O(log n)....