Ninja IT

B-tree

B-tree

B-tree là cấu trúc cây tìm kiếm tự cân bằng, đây là trường hợp tổng quát của cây nhị phân tự cân bằng. Thời gian tìm kiếm, chèn và xóa một node của B-tree trong thời gian logaric - O(log(n)).

Trong B-tree, các nút trong (nút không là lá) có thể có số lượng nút con khác nhau, giới hạn trong một khoảng nhất định. Khi dữ liệu được chèn vào hoặc xóa đi từ một nút, số nút con của nó thay đổi.

Khi sử dụng B-cây, ta định trước một số nguyên t. Mỗi nút trong của B-cây (trừ nút gốc) có từ t-1 tới 2t-1 khóa. Số lượng nút con của một nút đúng bằng số khóa của nút đó cộng một. Vì vậy, số lượng nút con của một nút trong là từ t tới 2t.

B-cây duy trì tính cân bằng bằng cách đảm bảo các nút lá đều có cùng độ sâu. Chiều cao của cây tăng dần dần khi các nút mới được chèn vào cây, nhưng con số này thay đổi rất chậm. Khi chiều cao của cây tăng lên, độ sâu của tất cả các nút lá tăng lên cùng một lúc.

Tham số quan trọng nhất cho B-cây không phải tổng thời gian tính toán, mà là số lần truy cập bộ nhớ. Số lần truy cập bộ nhớ trong mỗi thao tác trên B-cây tỉ lệ với chiều cao của cây.

B-cây có lợi thế hơn các cấu trúc dữ liệu tìm kiếm khác khi thời gian truy cập lớn hơn nhiều lần thời gian đọc dữ liệu liên tiếp nhau. Điều này thường xảy ra khi các nút được lưu trên bộ nhớ ngoài.

Thao tác

Có ba thao tác trên B-tree là tìm kiếm, chèn và xóa tương tự như cây nhị phân tìm kiếm. Độ phức tạp của từng thao tác này là O(log(n)).

B+ tree

B+ tree là một trường hợp đặc biệt của B-tree. Ngoài ra còn có các đặc điểm sau:

  • Tất cả các khóa đều được lưu lại một lần nữa ở nút lá.
  • Dữ liệu đi kèm với khóa cũng được lưu ở nút lá.
  • Các nút lá có con trỏ truy cập đến phần tử kế bên để tăng tốc truy cập tuần tự.

Cấu trúc B+ tree rất hay được sử dụng trong các hệ thống tập tin như NTFS và các hệ thống cơ sở dữ liệu như Microsoft SQL Server, Sqite có sử dụng cấu trúc B+ tree để index dữ liệu.

Khác với Hash table có thời gian truy cập là O(1) và thường lưu dữ liệu trên RAM (vì thời gian truy xuất một phần tử ngẫu nhiên là O(1)). B+ tree được tối ưu cho bộ nhớ ngoài, vì bộ nhớ ngoài có thể đọc dữ liệu liên tiếp nhanh hơn là truy cập một dữ liệu bất kỳ (sequential access nhanh hơn so với random access).