B-tree là gì

     

Trong bài viết này, ta sẽ cùng tìm hiểu về cấu trúc dữ liệu dạng cây B-tree. Ngoài ra, ta sẽ triển khai ví dụ về thao tác tìm kiếm, xóa và chèn trên cây B-tree bằng các hình ảnh minh họa.

Bạn đang xem: B-tree là gì

Cây B-Tree

B-tree là một loại cây tìm kiếm tự cân bằng đặc biệt, trong đó mỗi nút có thể chứa nhiều hơn một khóa và có thể có nhiều hơn hai nút con. Nó là một dạng tổng quát của cây tìm kiếm nhị phân.

Hình dưới đây sẽ minh họa ví dụ về cây B-tree như sau.

*

Tại sao cần sử dụng B-tree?

Nhu cầu về cây B xuất hiện cùng với sự gia tăng nhu cầu đòi hỏi ít thời gian hơn trong việc truy cập phương tiện lưu trữ vật lý như đĩa cứng. Các thiết bị lưu trữ thứ cấp chậm hơn nhưng có dung lượng lớn hơn. Cần có những kiểu cấu trúc dữ liệu như vậy để giảm thiểu việc truy cập vào đĩa.

Các cấu trúc dữ liệu khác như cây tìm kiếm nhị phân, cây AVL, cây đỏ đen chỉ có thể lưu trữ một khóa trong một nút. Nếu ta phải lưu trữ một số lượng lớn các khóa, thì chiều cao của những cây như vậy sẽ trở nên rất lớn và thời gian truy cập tăng lên.

Tuy nhiên, B-tree có thể lưu trữ nhiều khóa trong một nút và có thể có nhiều nút con. Điều này làm giảm chiều cao đáng kể cho phép truy cập đĩa nhanh hơn.

Xem thêm: Trường Thcs Trần Đại Nghĩa, Điểm Chuẩn Lớp 6 Thcs Trần Đại Nghĩa Tp Hcm

Các thuộc tính cây B-tree

Đối với mỗi nút x, các khóa được lưu trữ theo thứ tự tăng dần.Trong mỗi nút, có một giá trị kiểu boolean là x.leaf sẽ có giá trị là true nếu x là nút lá.Nếu n là bậc của cây, mỗi nút bên trong có thể chứa nhiều nhất n-1 khóa cùng với một con trỏ tới mỗi nút con.Mỗi nút ngoại trừ nút gốc có thể có nhiều nhất n nút con và tối thiểu là n/2 nút con.Tất cả các lá đều có cùng độ sâu (tức là chiều cao h của cây).Nút gốc có ít nhất 2 nút con và chứa tối thiểu 1 khoá.Nếu
*
, thì với bất kỳ cây B-tree với n khóa có chiều cao h và bậc nhỏ nhất là
*
,
*
.

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

1. Thao tác tìm kiếm

Tìm kiếm phần tử là hình thức tổng quát của việc tìm kiếm phần tử trong cây tìm kiếm nhị phân. Các bước được thực hiện như sau.

Bắt đầu từ nút gốc, so sánh k với khóa đầu tiên của nút. Nếu k = khóa đầu tiên của nút, trả về nút và chỉ số của nó.Nếu k.leaf có giá trị là true, trả về NULL (tức là không tìm thấy).Nếu k Nếu có nhiều hơn một khóa trong nút hiện tại và k > khóa đầu tiên, ta sẽ so sánh k với khóa tiếp theo trong nút. Nếu k Lặp lại các bước từ 1 đến 4 cho đến khi đạt được nút lá.

Ví dụ về thao tác tìm kiếm như sau. Giả sử ta sẽ tìm kiếm khóa k = 18 trong cây dưới đây với bậc 3.

*

Khóa k không có trong nút gốc nên ta sẽ so sánh với khóa của nút gốc là 13

*

Vì k > 13, ta sẽ chuyển đến nút con bên phải của nút gốc.

*

So sánh k với 15. Vì k > 15 nên ta sẽ so sánh k với khóa tiếp theo là 19.Vì k Và cuối cùng thì khóa k được tìm thấy là 18

Thuật toán cho thao tác tìm kiếm phần tử như sau.


Chuyên mục: Tổng hợp