여기서 B+ Tree에서 검색을 수행하는 방법을 살펴보겠습니다. B+ 트리 검색은 B+ 트리 쿼리라고도 합니다. 이 알고리즘은 B-Tree 쿼리와 매우 유사합니다. 또한 이것은 범위 쿼리를 지원합니다. 아래와 같은 B+ 트리가 있다고 가정합니다. -
B+ 트리의 예 -
검색 기술은 이진 검색 트리와 매우 유사합니다. 위의 트리에서 63을 검색한다고 가정합니다. 이제 루트에서 시작합니다. 이제 63은 루트 요소 60보다 크지만 75보다 작습니다. 따라서 요소 60의 오른쪽 자식으로 이동합니다. 오른쪽 자식은 63입니다. 그러나 B Tree를 사용하면 다음과 같이 됩니다. 결과. 이 경우 현재 노드가 내부 노드이므로 실제 데이터가 아닙니다. 먼저 오른쪽 자식으로 이동해야 합니다. 그리고 리프 수준에서 63을 레코드로 찾을 수 있습니다. 그것이 실제 결과일 것입니다.
63에서 78까지의 모든 요소를 검색하려면 각 요소를 하나씩 역추적할 필요가 없습니다. 초기 값의 리프 노드를 찾은 다음 연결된 리프 노드를 사용하여 78 이전의 모든 노드를 찾습니다. 그래서 범위 쿼리를 지원합니다.
B-Tree 내부의 요소를 검색하는 알고리즘을 살펴보겠습니다.
알고리즘
BPlusTreeSearch(루트, 키) -
입력 − 트리의 루트와 찾는 키
출력 − 키가 있는 노드의 값, 존재하지 않으면 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