'b+tree'에 해당되는 글 1건

  1. 2009.01.07 B+ TREE

B+ TREE

linux setup 2009. 1. 7. 11:31
1. Bayer & McCreight 가 제안한 균형 이진트리이다.
2. B-트리는 데이터베이스와 파일 시스템에서 널리 사용된다.
3. 삽입, 삭제 뒤에도 균형 상태 유지 한다.
4. 저장 장치의 효율성

[ 구 조 ]

사용자 삽입 이미지


[ 특 성 ]

- 가르키는 차수 ( 포인터의 갯수 ) 에 따라 m차 트리라고 부른다.

- B-Tree 는 공백이거나 높이가 1이상인 m-원 탐색트리
- 루트와 리프를 제외한 내부노드는 최소 [m/2 ], 최대 m 개의 서브트리를 가짐.
- 모든 리프노드는 같은 레벨에 있다.

[ 단 점 ]

- 구조 유지를 위해 추가적인 연산이 필요하다. 이러한 문제점을 해결위해 B* 트리를 고안했다.
  1) 삽입 : 노드의 분할
  2) 삭제 : 노드의 합병과 배분배 필요


[ B Tree - 노드 추가의 예 ]

사용자 삽입 이미지


B* 트리

B* Tree 는  Knuth 가 제안한 B-Tree의 변형으로, B-Tree의 문제점인 노드분할의 빈도를 줄이기 위해 고안되었되었다.

- 루트노드 : 리프가 아닌이상 최소 2개, 최대 2[2m-2/3]+1 의 서브트리를 갖는다.
- 루프, 리프를 제외한 노드 : 최소 [(2m-2)/3]+1 개의 서브트리를 갖는다.
                                       최소 [(2m-2)/3] 개,  최대 2[(2m-2)/3] 개의 Key 값을 가진다.
- 모든 리프노드는 같은 레벨에 있다.

B트리와 결정적으로 다른점은, 추가시에 노드가 가득찼으면 B트리는 분할하는데 반해, B*트리는 이웃노드에 빈곳이 있는지 검사하여 재분배시킨다. 만약, 비어있지 않다면 분할이 실행된다.


B+ 트리

B-트리는 순차검색이 난감하다. 이런 문제점을 해결하기 위해 B+트리는 B-트리와 리프노드를 LinkedList 로 연결함으로써 키검색과 순차검색이 모두 가능하게 수정된 트리이다.

'linux setup' 카테고리의 다른 글

grant privileges  (0) 2009.01.05
MySQL 5.0.45 + Windows XP sp2 설치 - 짧게  (0) 2009.01.01
Apache 2.2.4 + Windows XP sp2 설치 - 짧게  (0) 2009.01.01
Tomcat 6.0.13 + Apache 2.2.4 + MySQL 5.0.45+ WindowsXP  (0) 2009.01.01
Apache 설정  (0) 2008.12.11
Posted by 으랏차
,