1.B 트리
1) m-way 탐색트리
- m : 노드가 가질 수 있는 최대 자식의 개수
- 노드가 가질 수 있는 최대의 키 개수 : m-1
- 키의 의미 : 메모리 접근 횟수, 비교 연산 횟수의 차이
ex) 2-way : 노드 키가 1개임.
- 하드디스크에 저장된 노드를 읽어오는 메모리 접근 횟수, 읽어온 데이터를 찾고자 하는 키와 비교하는 연산 횟수 모두 트리높이와 동일함
- 트리 높이(h) = log n
ex) 4-way : 노드 키가 3개
- 트리 높이가 절반으로 줄어듦 : 메모리로의 접근 횟수 down
- 그러나 비교 연산 횟수는 증가.
- 하드디스크에 상주하는 자료구조 설계 시, 한 노드에 최대한 많은 키를 담아 메모리 접근 횟수를 줄이는 게 좋다.
- M-way 탐색트리
1) 서브 트리를 최대 m개 가짐
2) 한 노드에서 key는 정렬되어 있음
3) 어떤 키 K의 왼쪽 서브 트리의 모든 키는 K보다 작음
4) 어떤 키 K의 오른쪽 서브 트리의 모든 키는 K보다 큼
5) 서브트리도 m-way 트리임
2) B 트리 특징
- 2 <= 루트 노드의 서브트리 개수 <= m
- ⌈m/2⌉ <= 루트를 제외한 노드의 서브트리 개수 <= m
- ⌈m/2⌉ - 1 <= 루트를 제외한 노드의 키 개수 <= m-1
- 모든 리프노드는 같은 레벨에 존재
3) B 트리 연산
- 탐색 : BST 와 같음
3-1) 삽입연산
ex) 2-3 tree
- m = 3인 트리
- ⌈3/2⌉ <= 서브 트리 개수 <= 3
- 1 <= 노드 원소 개수 <= 2
- 모든 리프노드가 같은 레벨에 있음
- 실제 레코드를 노드에 저장하는 대신 키 옆에 그 키가 가리키는 레코드에 대한 참조를 저장
1) 빈 레코드에 1 삽입 => 첫번째 레코드가 ID 1을 가지고 삽입 : 키 1을 가진 루트 노드 생성됨(루트이자 리프)
2) 2 삽입 : 2-3 트리이므로 최대 키 2개 가질 수 있음. 1,2 모두 키가 됨.
3) 3 삽입 : 노드의 최대 키 개수 초과로 split 연산 발생
-> 가운데 있는 키를 새로운 노드에 삽입하여 부모 노드로 올림
4) 4 삽입 : 키 3이 있는 노드에 삽입되고 끝남
5) 5 삽입 : 키 3,4 있는 노드로 삽입되며 split 연산 발생됨
6) 6 삽입 : 부모 노드 최대 키 개수 초과로 부모노드 가운데 키를 조부모 노드로 올림. 높이 1개 추가됨
3-2) 삭제연산
- 키 삭제는 항상 리프노드에서 진행
- 리프노드가 아닌 노드에서 키 삭제 : 대체키를 바꾼 후 삭제
ex) 6삭제 : 6이 리프노드가 아니므로, 대체키는 6의 왼쪽 서브트리에서 가장 큰 값으로 선택(5) -> 5가 부모노드가 되면서 6은 삭제됨 - 2-3 트리는 서브트리의 개수가 최소 2개 이상 존재해야 함.
- donate 회전 연산
1) 왼쪽이나 오른쪽 형제 노드에 노드의 최소키 개수를 충족한 후 남는 키가 있는지 질의
ex) 2-3 트리의 노드 당 최소 키 개수 : 1
2) 남는 노드는 빈 노드로 donate 가능 : 부모노드와 값 비교 후 회전 연산
- donate 회전 연산
- merge 연산 : 부모에 있는 키 하나가 왼쪽, 오른쪽 자식 노드 가운데로 삽입됨 -> 트리 높이가 줄어듦.
- 삭제 연산 : donate, merge 연산을 연속적으로 수행
2. B+ 트리
- B 트리와 유사함.
- B 트리 : 레코드 포인터가 모든 노드 안에 있는 키 옆에 바로 있음.
- B+ 트리
- 인덱스 노드
- 레코드 포인터가 없고 대신 다른 인덱스 노드나 데이터 노드에 대한 참조만 있음.
- 인덱스 노드에서는 키 중복 없음. 데이터 노드에서는 키 중복됨.
- 데이터 노드 :
- 각 데이터 노드에는 모두 레코드 포인터 존재
- 모든 키가 다 있음
- 실제 데이터를 가리키고 있음.
- 이중 연결 리스트로 이어져 있음
3. B 트리로 인덱스 만들기
- 데이터베이스에서 테이블을 만들면 자동으로 B+ 트리로 구성된 인덱스 생성됨
ex) id가 2인 데이터 탐색 : ID가 B트리의 키임SELECT * FROM example
WHERE ID = 2
ex) 이름 탐색하는 경우 : 검색 속도 향상을 위해 이름 인덱스를 생성
CREATE INDEX idx_name ON example(name);
SELECT * FROM example WHERE name LIKE '이순신';
- name 이라는 인덱스 생성
- 추가적으로 해당 인덱스 사용할 게 아니라면, 반드시 삭제해야 함 : 레코드의 삽입, 삭제 연산(split, donate, merge) 성능 저하됨
hello world!