B-cây

Trong khoa học máy tính, B-cây là một cấu trúc dữ liệu dạng cây cho phép tìm kiếm, truy cập tuần tự, chèn, xóa trong thời gian lôgarit. B-cây là một tổng quát hóa của cây nhị phân tìm kiếm, trong đó một nút có thể có nhiều hơn hai con. Không như cây nhị phân tìm kiếm tự cân bằng, B-cây được tối ưu hóa cho các hệ thống đọc và ghi dữ liệu lớn. Nó thường được dùng trong các cơ sở dữ liệu và hệ thống tập tin.

Tổng quan

Trong B-cây, 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 đó, để duy trì số nút con trong khoảng đã định, các nút trong có thể được hợp hai làm một hoặc chia đôi. Vì số lượng nút con có thể nằm trong một khoảng lớn, B-cây không cần tái cân bằng thường xuyên như cây nhị phân tìm kiếm, nhưng lại sử dụng bộ nhớ lãng phí hơn do các nút không chứa tối đa dữ liệu.

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. Hệ số 2 đảm bảo rằng các nút có thể được chia đôi hoặc kết hợp. Với một nút trong có 2t-1 khóa, ta có thể lấy khóa giữa trong 2t-1 khóa chèn vào nút cha và chia 2t-2 khóa còn lại vào hai nút mới, mỗi nút t-1 khóa. Tương tự như vậy, khi một nút và nút kế bên đều có t-1 khóa, ta có thể kết hợp hai nút cùng với một khóa từ nút cha thành một nút mới có 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.

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. Bằng cách tăng số lượng nút con của mỗi nút, chiều cao của cây giảm xuống và số lần truy cập cũng giảm. Thêm vào đó, số thao tác tái cân bằng cây cũng giảm đi. Thông thường, tham số t (quyết định số khóa của mỗi nút) được chọn tùy theo lượng thông tin trong mỗi khóa và kích thước mỗi khối đĩa.

Các biến thể

Thuật ngữ B-cây có thể được dùng để chỉ một thiết kế cụ thể, cũng có thể được dùng để chỉ một lớp các thiết kế. Theo nghĩa hẹp, B-cây lưu một số khóa ở các nút trong và không lưu bản sao của các khóa đó ở nút lá. Theo nghĩa rộng, nó còn bao gồm những biến thể khác như B⁺-cây hay B^*-cây.

• Trong B⁺-cây, các nút trong lưu bản sao của khóa. Tất cả các khóa, cùng với dữ liệu đi kèm được lưu ở các nút lá. Ngoài ra các nút lá còn có con trỏ đến các nút lá kế bên để tăng tốc truy cập tuần tự.
• B^*-cây thực hiện nhiều thao tác tái cân bằng hơn để lưu trữ dự liệu dày đặc hơn. Mỗi nút trong khác gốc phải đầy tới hai phần ba thay vì chỉ một nửa như trong B-cây.

Chi tiết kĩ thuật

Định nghĩa

Có nhiều định nghĩa khác nhau của B-cây trong các tài liệu. Sau đây là một định nghĩa.

1. Mỗi nút x chứa
   1. số n[x] là số khóa lưu tại x.
   2. n[x] khóa, theo thứ tự tăng dần.
2. Mỗi nút trong x chứa n[x]+1 con trỏ tới các nút con của x.
3. Mỗi khóa tại x có giá trị nằm giữa giá trị các khóa tại hai cây con tương ứng của x: khóa thứ i của x lớn hơn hoặc bằng mọi khóa ở cây con thứ i của x và nhỏ hơn hoặc bằng mọi khóa ở cây con thứ i+1 của x.
4. Mọi nút lá đều có cùng một độ sâu.
5. Số khóa của mỗi nút nằm trong một khoảng định trước. Khoảng này được quyết định bởi tham số t≥2.
   1. Mỗi nút trong khác gốc có ít nhất t-1 khóa. Nếu cây khác rỗng thì nút gốc phải có ít nhất một khóa.
   2. Mỗi nút có tối đa 2t-1 khóa.

Độ phức tạp tính toán

Cũng như các thuật toán cho bộ nhớ ngoài khác, tham số quan trọng nhất cho B-cây không là 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. Một B-cây với n nút có chiều cao không quá $\log _{t}{\frac {n+1}{2}}$.

Các thao tác trên B-cây

Tìm kiếm

Tìm kiếm trên B-cây cũng tương tự như tìm kiếm trên cây nhị phân tìm kiếm. Giả sử giá trị cần tìm là v. Thuật toán xuất phát từ nút gốc và tìm từ trên xuống dưới. Tại nút x, thuật toán chọn nút con thứ i sao cho mọi khóa tại x với thứ tự nhỏ hơn i đều nhỏ hơn hoặc bằng v, và mọi khóa tại x với thứ tự lớn hơn hoặc bằng i đều lớn hơn hoặc bằng v.

Chèn

Để chèn thêm một khóa mới, trước tiên thực hiện thao tác tìm kiếm để tìm đến nút lá ở vị trí cần chèn. Nếu nút lá đã đầy (chứa 2t-1 khóa), thuật toán lấy khóa ở giữa ra rồi chia các khóa còn lại vào hai nút mới, mỗi nút có t-1 khóa. Sau đó, đặt khóa ở giữa vừa lấy ra vào nút cha để làm điểm chia cho hai nút mới vừa tạo. Nếu nút cha cũng đầy thì lặp lại thao tác chia đôi như trên (có thể phải lặp lại cho tới nút gốc, tạo ra nút gốc mới).

Có thể cải tiến để thuật toán chỉ phải đi từ trên xuống đúng một lần bằng cách chia đôi ngay các nút đầy gặp được trên đường đi khi thực hiện thao tác tìm kiếm.

Bài báo ban đầu

• Bayer, Rudolf; McCreight, E. (1970), Organization and Maintenance of Large Ordered Indices, Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories

• Bayer, Rudolf (1971), “Binary B-Trees for Virtual Memory”, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California