|
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 |
