여기서 B-Tree에서 검색을 수행하는 방법을 살펴보겠습니다. B-트리 검색은 B-트리 쿼리라고도 합니다. 아래와 같은 B-트리가 있다고 가정합니다. -
B-트리의 예 -
검색 기술은 이진 검색 트리와 매우 유사합니다. 위의 트리에서 66을 검색한다고 가정합니다. 따라서 루트에서 시작합니다. 이제 66은 루트 요소 46보다 큽니다. 따라서 루트의 오른쪽 자식으로 이동합니다. 그런 다음 오른쪽 자식에는 둘 이상의 요소가 있습니다. 요소는 정렬되며 [56, 81]입니다. 대상 키는 56보다 크고 81보다 작으므로 56과 81 사이에 있는 하위 트리로 들어갑니다. 그런 다음 리프 수준으로 이동했습니다. 그 시점에서 우리는 요소 66을 얻었습니다.
B-Tree 내부의 요소를 검색하는 알고리즘을 살펴보겠습니다.
알고리즘
BTreeSearch(루트, 키) -
입력 − 트리의 루트와 찾는 키
출력 − 키가 있는 노드의 값, 존재하지 않으면 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