Xem B+ Tree. Là phiên bản mở rộng của B-Tree. Hỗ trợ chèn, xóa, tìm kiếm tốt hơn B-Tree.
B-Tree: khóa và record lưu ở cả nút nội và lá. B+ Tree: record chỉ lưu ở lá, nút nội chỉ lưu khóa. Các lá B+ Tree liên kết như linked list.
Ví dụ B+ Tree
Hỗ trợ tìm kiếm, chèn, xóa. Trong nút, khóa sắp xếp. Phần tử i có con trái (giá trị nhỏ) và con phải (lớn).
Ưu điểm so với B-Tree
- Record truy xuất cùng số lần truy cập đĩa.
- Chiều cao cây cân bằng, thấp hơn B-Tree.
- Lá liên kết như linked list → duyệt tuần tự.
- Khóa dùng cho chỉ mục.
- Tìm kiếm nhanh hơn vì dữ liệu chỉ ở lá.