Ở đây chúng ta sẽ xem B-Trees là gì. Cây B là cây tìm kiếm m-way chuyên biệt. Điều này có thể được sử dụng rộng rãi để truy cập đĩa. Một cây B thứ tự m, có thể có tối đa m-1 khóa và m con. Điều này có thể lưu trữ một số lượng lớn các phần tử trong một nút duy nhất. Vì vậy chiều cao tương đối nhỏ. Đây là một lợi thế lớn của B-Trees.
B-Tree có tất cả các thuộc tính của cây một chiều. Nó có một số thuộc tính khác.
-
Mỗi nút trong B-Tree sẽ chứa tối đa m con
-
Mỗi nút ngoại trừ gốc và lá, có thể chứa ít nhất m / 2 nút con
-
Các nút gốc phải có ít nhất hai nút con.
-
Tất cả các nút lá phải có cùng cấp độ
Ví dụ về B-Tree
Điều này hỗ trợ các thao tác cơ bản như tìm kiếm, chèn, xóa. Trong mỗi nút, mục sẽ được sắp xếp. Phần tử ở vị trí tôi có con trước và sau nó. Vì vậy, những đứa trẻ được nuôi dưỡng trước đây sẽ giữ những giá trị nhỏ hơn và những đứa trẻ hiện tại bên phải sẽ giữ những giá trị lớn hơn.