Ở đâ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. Thuật toán này rất giống với truy vấn của B-Tree. Hơn nữa, điều này hỗ trợ truy vấn phạm vi. 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 kiếm 63 từ cây trên. Vì vậy, chúng tôi sẽ bắt đầu từ gốc, bây giờ 63 lớn hơn phần tử gốc 60 nhưng nhỏ hơn 75. Vì vậy, chúng tôi sẽ chuyển sang con bên phải của phần tử 60. Con bên phải là 63. Nhưng nếu chúng ta sử dụng B Tree, thì đó sẽ là kết quả. Trong trường hợp này vì nút hiện tại là nút nội bộ, thì đó không phải là dữ liệu thực tế. Trước hết chúng ta phải chuyển đến đúng đứa trẻ. Và ở cấp độ lá, chúng ta có thể tìm thấy 63 là kỷ lục. Đó sẽ là kết quả thực tế.
nếu chúng ta muốn tìm kiếm tất cả các phần tử từ 63 đến 78, thì chúng ta không cần phải dò lại từng phần tử, từng phần tử một. Chúng tôi tìm nút lá của giá trị ban đầu, sau đó bằng cách sử dụng các nút lá được liên kết, chỉ cần tìm tất cả các nút trước 78. Vì vậy, điều này hỗ trợ truy vấn phạm vi.
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
BPlusTreeSearch (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
Apply binary search on records if record with the ‘key’ is found, then return required record else if current node is leaf node, and key is not found, then return null