B+ Tree 란?

소개글

B+ Tree 란?에 대한 보고서 자료입니다.

본문내용

B Tree
보통 2진 탐색 트리
만약 노드를 키의 올림 차순(또는 내림차순)으로 삽입하면 오른쪽(또는 왼쪽)만으로 가지를 펼치며 트리 라기 보다는 리스트에 가까우며 탐색이 두드러지게 느려진다(O(lon n) 이 O(n)이 된다).
그래서 어떤 순서대로 키를 삽입해도 밸런스가 붕괴되지 않는 트리구조가 여러가지 연구 되고 있다.
R.Bayer가 만든 B-Tree도 그 하나이다.
B tree나 그 변형은 특별히 디스크 등의 2차 기억으로 실현하는데 좋으므로 테이터베이스 소프트웨어 등에 종종 이용된다.
검색
루트에서 시작하여 페이지마다 한다.
그 페이지에 없으면 키의 대소 관계로 어느 페이지를 조사하면 된다.
리프 노트에서 나오는 포인터는 모두 특별한 값 null로 하면, null을 만나면 그 키는 등록되지 않은 것을 알 수 있다.
삽입
탐색과 마찬가지로 루트에서부터 조사해 가며 삽입하고 싶은 키가 이미 존재 하면 아무것도 하지 않고 리턴한다.
그렇지 않으면 반드시 null에 도착하므로 그 앞페이지(리프)로 리턴하며 그 페이지가 가득 차 있지 않았으면 거기에 저장한다.
그 페이지가 가득 찼으면(이미 2m개가 들어가 있다). 새로운 키를 넣으면 2m+1rork 되므로 그 2m+1개 중 작은 m개는 원래의 페이지에 남고, 큰 m개로 새로운 페이지를 만들며 중앙의 한 개는 원래의 페이지에서 근을 향해서 한걸음 리턴한 페이지에 추가한다.
키를 한 개 추가하면 포인터도 한 개 증가하므로 조금 전에 만든 새로운 페이지를 가리키도록 한다.
그렇게 함으로써 다시 정원 오버 페이지가 생기면 위와 같이 반복한다.
삭제
리프에 없는 페이지의 키에 대해서는 그 키 다음에 큰 키는 반드시 잎에 있으므로 양쪽 항목을 넣어 바꾸며 삭제는 반드시 리프에서 일어나도록 할 수 있다.
잎에서 키를 삭제하여 키가 m개 미만으로 되지 않으면 한걸음 앞(루트에 가까운 쪽)페이지로 리턴하며 너무 성기게 된 페이지의 좌우 어느쪽 페이지에서 한 개의 키를 가져 온다.
좌우 어느 쪽에도 키가 m개밖에 없으면 어느 쪽과 결합해서 페이지수를 감소한다.

키워드

B+,   tree,   정의,   검색,   삽입