B Tree는 자식 노드의 개수가 최대 2개인 이진트리(Binary Tree)를 보완하고자 나온 자식의 개수가 2개 이상인 트리이다. B tree는 최대 M개의 자식을 가질 수 있고 이진트리와 달리 하나의 노드의 여러가지 key값을 가질 수 있으며 최대 M-1개의 key값을 가질 수 있다.
- 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.
- 부모 노드의 key들을 오름차순으로 정렬한다.
- 정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다.
- 각 노드는 최소 ⌈M/2⌉개의 자식 노드를 가진다. (루트 노드와 leaf 노드 제외)
- 각 노드는 최소 ⌈M/2⌉-1개의 키를 가진다. (루트 노드 제외)
B tree 데이터 삽입
- 추가는 항상 leaf노드에 한다.
- 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.
- 노드에는 오름차순으로
특징
- b tree의 모든 leaf 노드들은 같은 레벨에 있다. => balanced tree
이진트리의 경우 최악의 경우일때 O(N), 비트리는 avg/worst case O(lon N)
B tree 데이터 삭제
- 삭제도 항상 leaf노드에서 발생
- 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
1. key의 수의 여유있는 형제의 지원을 받는다.(동생 먼저)
- 동생이 여유가 있으면
- 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다
- 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다.
- 형이 여유가 있으면
- 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다.
- 원래 그 자리에 있던 key를 부모 노드의 나와 형 사이에 둔다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다. (동생 먼저)(합칠때는 왼쪽 먼저)
-
3. 2번 후 부모의 문제가 있다면 거기서 다시 재조정한다.
- 부모가 root 노드가 아니라면 그 위치에서 부터 다시 1번부터 재조정한다.
- 부모가 root노드고 비어있다면 부모노드를 삭제, 직전에 합쳐진 노드가 root 노드가 된다.
internal 노드 데이터 삭제
- leaf 노드에서 삭제하고 필요하면 재조정
- internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
- leaf 노드에 있는 데이터 증에 어떤 데이터와 위치를 바꿔줄 것인지가 이슈
- -> 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.- 선임자(predecessor): 나보다 작은 데이터들중 가장 큰 데이터
- 후임자(successor): 나보다 큰 데이터들 중 가장 작은 데이터
- 선임자나 후임자는 항상 leaf노드에 있음
장단점
장점 - 노드의 삽입/삭제 후에도 균형 트리 유지로 균등한 응답 속도 보장
- 시간 복잡도 : O(logN)
단점 - 삽입/삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행 필요
활용
- DBMS나 파일 시스템의 인덱스 자료구조로 활용
- 검색엔진, 패턴 매칭 등 성능이 일정하면서 빠른 탐색이 요구되는 분야에서 활용
인덱스
평균 시간 복잡도
일반적인 Tree는 탐색하는 시간 복잡도가 O(logN)을 갖는다. 그러나 일반적이지 않고 특수한 경우는 어떨까?
최악 시간 복잡도
트리 노드의 요소가 한 쪽으로 쏠리게 되면, 시간 복잡도가 O(N)을 갖게 되어 List와 별반 다를 것이 없어진다. 이러한 경우를 방지하기 위하여 인덱스에서는 밸런스 트리를 선택하였다.
밸런스 트리
트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재 정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다. 항상 양쪽 자식의 밸런스를 유지하므로 무조건 O(logN)의 시간 복잡도를 보장한다. 다만 재 정렬되는 작업으로 인해 노드 삽입 및 삭제 시 일반적인 트리보다 성능이 떨어진다. 그러므로 밸런스 트리는 삽입/삭제의 성능을 희생하고 탐색에 대한 성능을 높였다고 볼 수 있다.
해시테이블
사실 탐색 시간이 빠른 것으로 인덱스 자료 구조를 선택한다면, 시간복잡도가 O(logN)인 다른 자료 구조를 사용하거나 시간복잡도가 O(1)인 해시 테이블을 사용하는 것이 더 빠를 수 있다.
but 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조인데 이러한 특성상 해시가 등호(=) 연산에만 특화되었기 때문에 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
인덱스
인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조이다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함꼐 저장된다. 또한, 인덱스 생성 시 오름차순으로 정렬하기 때문에 정렬된 주소체계라고 표현할 수 있다.
인덱스를 책에서의 목차라고 생각하면 이해하기 쉽다. 책에서 원하는 내용을 찾을 때 목차나 색인을 이용하면 훨씬 빠르게 찾을 수 있듯이 테이블에서 원하는 데이터를 찾기 위해 인덱스를 이용하면 빠르게 찾을 수 있다. 그러므로 데이터=책의 내용, 인덱스=책의 목차, 물리적 주소=책의 페이지 번호라고 생각하면 된다.
