Ở đây chúng ta sẽ thấy cách thực hiện tìm kiếm trong B-Tree. Tìm kiếm B-Tree còn được gọi là B-Tree Querying. Giả sử chúng ta có một cây B như bên dưới -
Ví dụ về B-Tree -
Kỹ thuật tìm kiếm rất giống với cây tìm kiếm nhị phân. Giả sử chúng ta muốn tìm 66 từ cây trên. Vì vậy, chúng ta sẽ bắt đầu từ gốc, bây giờ 66 lớn hơn phần tử gốc 46. Vì vậy, chúng ta sẽ chuyển đến phần tử con bên phải của gốc. Sau đó, con bên phải có nhiều hơn một phần tử. Các phần tử được sắp xếp, chúng là [56, 81]. Khóa mục tiêu của chúng ta lớn hơn 56, nhưng nhỏ hơn 81, vì vậy chúng ta sẽ nhập vào cây con, nằm trong khoảng từ 56 đến 81. Vì vậy, sau đó chúng ta đã chuyển sang cấp độ lá. Tại thời điểm đó, chúng tôi có phần tử 66.
Hãy để chúng tôi xem thuật toán tìm kiếm phần tử bên trong B-Tree.
Thuật toán
BTreeSearch (root, key) -
Đầu vào - Gốc cây và chìa khóa để tìm
Đầu ra - Giá trị của nút có khóa, nếu không có thì trả về null
x := Read root if x is an index node, then if there is an object o in x, such that o->key = ‘key’, then return o->val Find the child of x, as x->child[i], whose key range is containing ‘key’ return BTreeSearch(x->child[i], key) else if there is an object o in x, such that o->key = ‘key’, then return o->val, else return null end if end if