B-Tree 에 대하여

소개

B-tree에 대한 정의, 기원 등을
보기쉽게 정리한 자료입니다.

목차

Ⅰ> B-Tree의 기원 ‧ 어원
Ⅱ> B-Tree 의 정의
Ⅲ> B-Tree 의 구조
Ⅳ> B-Tree 구조의 단점
Ⅴ> B* Tree
Ⅵ> B+ Tree
Ⅶ> B-tree 의 인덱스 구조 예
Ⅷ> 참고 - 알고리즘

본문내용

Ⅱ> B-Tree 의 정의
● 이진트리(Binary Tree)와 다르며, 균형트리(Balanced Tree)이다. 이진트리는 차수가 2이하지만, 균형트리는 2이상이 가능하다. 따라서 B-tree는 2이상이 가능하다.
● 대용량의 데이터를 효율적으로 관리하기 위해 고안된 트리 형태의 자료 구조이다.
● 인덱스 개념의 특수한 응용의 하나이다.
● 데이터 레코드의 순차적 처리와 직접적 처리를 모두 지원하는 다단계 인덱스(multi-level index)이다.
● m-원 트리의 단점인 한 쪽으로 편중된 트리를 생성되는 경우를 보완하고자 루트노드로부터 잎노드(leaf노드)의 레벨을 같도록 유지한 트리이다. 즉 잎노드가 루트노드로부터 같은 거리에 있어야 한다는 것이다. 모든 잎노드가 루트노드로부터 같은 거리에 있으므로 어느 잎노드를 탐색하든 처리횟수와 탐색시간이 같아지게 된다.
● 항상 균형을 유지해야하므로 삽입, 삭제가 일어날 때 트리의 균형을 유지하기 위해서 보조연산이 필요하다.
● 노드의 차수가 여유가 있으면 보조연산이 필요없지만, 차수가 꽉차면 잎노드의 중간값을 부모노드로 하여 두 갈래로 분열한다.
● Root 노드는 최소한 두 개의 서브트리(종속트리)를 가져야 한다. 단 트리에 root 만 있을 경우 서브트리는 없다. 이 조건에 의해 tree가 처음부터 분기하도록 한다.
● B-트리는 데이터베이스와 파일 시스템에서 널리 사용된다.
● B-트리를 보완(변형)해서 B+ Tree, B* Tree 가 있다.

참고자료

· http://ask.nate.com/qna/view.html?n=6043015&sq=b-tree
· http://www.ssiso.net/cafe/club/club1/board1/content.php?board_code=oracle
· http://hkless.sch.ac.kr/free_board/upload/%c6%AE%B8%AE%C0%CC%B7%D0%28%BC
· http://sweeper.egloos.com/896423
· http://cafe.naver.com/sqlserver.cafe?iframe_url=/ArticleRead.nhn%3Farticleid=722
· http://kr.blog.yahoo.com/badadult/1029