Database hay gặpCả hai là cây cân bằng, nhiều nhánh, giữ dữ liệu luôn sắp xếp và cho tra cứu ở độ sâu O(log n). Khác nhau ở chỗ lưu dữ liệu:
- B-tree: khóa và con trỏ dữ liệu nằm ở mọi node, kể cả node trong.
- B+ tree: node trong chỉ chứa khóa để định tuyến, còn toàn bộ dữ liệu nằm ở node lá, và các lá được nối thành danh sách liên kết.
Vì sao index thích B+ tree:
- Node trong không chứa data nên chứa được nhiều khóa hơn mỗi trang → cây thấp hơn → ít lần đọc đĩa hơn.
- Lá nối chuỗi giúp quét theo dải và ORDER BY rất nhanh: tìm điểm đầu rồi đi dọc theo lá, không cần quay lại node trên.
- Mọi tra cứu đều đi hết tới lá nên chi phí ổn định, dễ dự đoán.
Trên thực tế, index mặc định của PostgreSQL, MySQL... là biến thể B+ tree đúng vì các lợi thế cho quét dải và số lần truy cập đĩa.