[FP] 06. 인덱스 구조

인덱스

화일의 레코드들에 대한 효율적 접근을 위한 조직

<키 값, 레코드 주소(포인터)>쌍으로 구성

 

키 값의 유형에 따른 인덱스

• 기본 인덱스 : 키 값이 기본 키인 인덱스
• 보조 인덱스 : 기본 인덱스 이외의 인덱스

화일 조직에 따른 인덱스

• 집중 인덱스 : 화일의 데이터 레코드들의 물리적 순서와 인덱스 엔트리 순서가 동일한 인덱스
• 비집중 인덱스 : 집중 인덱스가 아닌 인덱스

데이터 범위에 따른 인덱스

• 밀집 인덱스 : 데이터 레코드 하나에 하나의 인덱스 엔트리가 만들어지는 인덱스 (역 인덱스라고도 함)
• 희소 인덱스 : 데이터 레코드 그룹 또는 데이터 블록에 하나의 엔트리가 만들어지는 인덱스

---

이원 탐색 트리 (binary search tree)

이진 트리

• 유한한 노드를 가진 트리
• 공백이거나 루트와 두 개의 분리된 이진트리(왼쪽, 오른쪽 서브 트리)로 구성

이원 탐색 트리

• 이진 트리
• 각 노드 Ni는 레코드키 Ki와 이 키를 가지고 있는 레코드 포인터를 포함

공백이 아닌 이원 탐색 트리의 성질

• 모든 노드는 상이한 키 값을 가진다
• 루트 노드 Ni의 왼쪽 서브 트리에 있는 모든 노드의 키 값들은 루트 노드의 키 값보다 작다.
• 루트 노드 Ni의 오른쪽 서브 트리에 있는 모든 노드의 키 값들은 루트 노드의 키 값보다 크다.
• 왼쪽 서브 트리와 오른쪽 서브 트리 모두 이원 탐색 트리이다.

---

---

AVL 트리

AVL 높이 균형 이진 트리

• 삽입, 삭제, 검색 시간 : O(log N) - 트리의 일부만 재균형시키면서 트리 전체가 균형을 계속 유지할 수 있게 함

AVL 트리란?

• 각 노드의 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이원 탐색 트리
• 공백 서브트리 높이는 -1

균형 인수란? (Bf) (Balance factor)

• 왼쪽 서브 트리 높이에서 오른쪽 서브 트리의 높이를 뺀 수
• -1, 0, 1 이면 AVL 성질을 만족
• AVL 트리의 모든 노드는 AVL 성질을 만족한다.

AVL 트리에서의 검색

• 일반 이원 탐색 트리와 동일
• 시간 복잡도 : O(log N)

AVL 트리에서의 삽입

• 삽입되는 노드에서부터 루트까지 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있음
• 노드 삽입으로 균형 인수가 -1, 0, 1을 벗어나면 트리 구조를 조정해야 함

AVL 성질을 만족하지 않는 노드가 출현하는 경우

1. LL : x의 왼쪽 자식(L)의 왼쪽 서브 트리(L)에 노드를 삽입
2. RR : x의 오른쪽 자식(R)의 오른쪽 서브 트리(R)에 노드를 삽입
3. LR : x의 왼쪽 자식(L)의 오른쪽 서브 트리(R)에 노드를 삽입
4. RL : x의 오른쪽 자식(R)의 왼쪽 서브 트리(L)에 노드를 삽입

회전(rotation)

• 불균형이 발생할 때 트리 구조를 변경하여 균형을 잡아주는 것
• 단순 회전 : 한 번의 회전만 필요 (LL, RR) / 탐색 순서를 유지하면서 부모와 자식 원소의 위치를 교환
• 이중 회전 : 두 번의 회전이 필요 (LR : RR 후 LL) (RL : LL 후 RR)

---

노드 삽입에 따른 균형 인수의 변화

• 새로 노드를 삽입할 때, BF에 영향을 받는 노드는 오직 <새 노드 ~ 루트> 의 경로 상에 있는 노드들이다.
• 새로운 노드를 왼쪽 서브 트리로 삽입하면 그 부모 노드의 BF는 하나 증가 (+1) / 오른쪽이면 하나 감소 (-1)
• 이때 BF가 0이 되면 BF 조정은 종료. 아니면 그 부모 노드의 BF를 변경
• 즉, 자기가 부모 노드의 왼쪽 서브 트리이면 BF를 +1, 오른쪽이면 -1를 하면서 루트까지 따라가면서 조정 작업 계속

높이 균형 이진 트리의 높이

• N개의 노드를 가진 높이 균형 이진 트리는
  완전 균형 이진 트리보다 45%이상 높아지지 않음
  log(N+1)≤h ≤1.4404log(N+2)-0.328
• 높이 균형 이진 트리 VS 완전 균형 이진 트리
  O(1.4 log N) VS O(log N) -> 높이 균형이 더 탐색 시간이 길다
  -> 트리의 전체 재균형을 수행하지 않기 때문
• 수 백만 개의 노드로 구성된 AVL 트리가 디스크에
  저장된 상태에서의 노드 탐색은 많은 횟수의 디스크
  접근을 요구한다. 그래서 m-원 탐색 트리가 등장

---

m-원 탐색 트리

이원 탐색 트리보다 높은 분기율, m개의 서브 트리
장점 : 트리의 높이가 감소 = 노드의 탐색 시간 감소
단점 : 삽입, 삭제 시 트리의 균형을 유지하기 위한 복잡한 연산이 필요

 

m-원 탐색 트리의 성질

1. 노드의 구조 : <n, P0, K1, P1, K2, P2, …, Kn, Pn> (n은 키 값의 수, P는 서브 트리의 포인터, K는 키 값)
2. 한 노드에 있는 키 값들은 오름차순으로 되어 있다.
3. Pi 가 지시하는 서브 트리의 모든 노드의 키 값 < Ki+1
4. Pn 이 지시하는 서브 트리의 모든 노드의 키 값 > Kn
5. Pi 이 지시하는 서브 트리들은 모두 m-원 트리이다. 

m-원 탐색 트리의 탐색 시간

• 탐색 경로 길이(높이)에 비례
• 각 레벨에서는 한 개의 노드만 탐색
• 분기율(m)을 크게 하면 트리의 높이가 낮아짐

m-원 탐색 트리는 한 노드에 m-1개 키 값을 저장

• 높이가 h이면 -> mh-1 개의 키 값을 저장
• 예> 4-원 탐색 트리 : 높이가 3이면 최대 4^3-1 = 63개 키 값을 저장

N개의 키를 가진 m-원 탐색 트리

• 최소 높이 h : ⌈ logm (N+1) ⌉
• 최대 탐색 시간 : Ｏ(logm (N+1))

키 값 Ki : ( Ki , Ai )를 의미 : ( 키 - 포인터 ) 쌍
Ki를 포함하고 있는 데이터 레코드의 주소

---

B-트리

균형 m-원 탐색 트리 : 가장 많이 사용되는 인덱스 방법, 효율적인 균형 알고리즘을 제공

---

B-트리의 삭제

재분배

• 트리 구조가 변경되지 않음 (3-원 B-트리면 1)
• 해당 노드의 오른쪽, 왼쪽 형제 노드 중 최소 키 값보다 많은 수의 키 값을 가진 노드에서 키 값을 하나 차출
• 부모 노드에 있는 키 값을 언더플로가 일어난 노드로 이동, 그 빈 자리로 차출된 키 값을 이동

합병

• 트리 구조가 변경됨
• 재분배가 불가능한 경우에 적용 (두 형제 노드가 최소의 키 값만을 가질 때)
• 언더플로가 된 노드의 오른쪽(또는 왼쪽) 형제 노드에 있는 키 값들과 이 두 노드를 분리시키는 부모 노드의 키 값을 합치고 트리 구조를 조정, 합병으로 생긴 빈 노드는 제거
• 이 합병 작업은 루트 노드까지 연쇄적으로 파급 가능, 이 경우 트리의 레벨이 하나 감소

---

B*-트리

B-트리의 문제점

• B-트리 구조 유지를 위해 추가적인 연산이 필요 (삽입 : 노드의 분할, 재분배 / 삭제 : 노드의 합병, 재분배)
• B*-트리는 B-트리의 성능 개선을 위해 Knuth가 제안한 B-트리의 변형이다. 

B*-트리의 성질

 

삽입으로 인한 노드 분할의 빈도를 축소

• 노드가 오버플로되면 즉시 분할하는 대신에 오버플로된 키 값과 포인터를 바로 인접한 형제 노드의 여유 공간을 이용해 재분배한다. 
• 인접 형제 노드가 모두 만원이면 두 인접 형제 노드의 키 값들을 3개의 노드로 분할한다.
• 한 노드가 만원이 되더라도 다른 인접 형제 노드가 만원이 될 때까지 분할은 지연
• 각 내부 노드는 항상 2/3 이상이 키 값으로 채워진다.
• 같은 키 값의 수에 대해 B-트리보다 적은 수의 노드가 필요하다. 

B*-트리의 삽입

 

B*-트리의 삭제

B-트리에서의 삭제와 비슷. 키 값 삭제로 최소 키 값 수가 유지되지 않으면

1. 형제 노드로부터 재분배를 받도록 시도
2. 형제 노드에 여유 키 값이 없으면 3개의 노드를 2개의 노드로 합병 -> 트리의 높이가 한 레벨 낮아질 수 있음

---

트라이 (Trie)

re T R I E v a l의 약자

키를 구성하는 문자나 숫자의 순서를 이용해 키 값을 검색할 수 있는 자료 구조

m-진 트리이지만 m-원 탐색 트리는 아님 : 키 값의 배열 순서가 다름

 

m-진 트라이 (m-ary trie)

• 차수 m : 키 값을 표현하기 위해 사용하는 문자의 수, 즉 기수(radix). 숫자는 m=10, 알파벳은 m=26
• m-진 트라이는 m개의 포인터를 표현하는 1차원 배열. 각 원소(포인터)는 기수의 원소에 1:1로 대응

트라이의 특징

• 트라이의 높이 = 키 필드의 길이
• 10진 트라이의 레벨 j의 포인터 pi는 j번째 숫자가 i인 모든 키 값을 나타내는 서브 트라이를 가리킨다.
• 레벨 3에 있는 p4는 키 값의 3번째 숫자가 4인 키 값을 가진 서브 트라이를 가리킴
• 해당 숫자가 없을 때는 Null 포인터로 표시
• 키 값 : 루트 노드의 pi에서 리프 노드의 pj까지의 경로를 각 포인터에 대응하는 기수 원소로 표현한 것
• 리프 노드에는 해당 키 값을 가진 레코드의 주소가 저장됨
• 키 검색뿐만 아니라 키의 존재 유무를 빠르게 결정
• 트라이에서 Null 포인터만 가지고 있는 공백 노드는 생성하지 않음

m-진 트라이의 연산

• 검색
   - 검색은 리프에서 종료되거나, 키 값이 없을 때 중간 노드에서 종료
   - 검색 속도는 키 필드의 길이(트라이의 높이)에 비례
   - 최대 검색 비용은 키 필드의 길이
   - 장점 : 균일한 탐색 시간
   - 선호 이유 : 없는 키에 대한 빠른 검색
• 삽입
   - 새로운 키 값이 삽입되어야 할 노드를 검색
   - 리프 노드에 새 레코드의 주소나 존재 표시를 삽입
   - 리프 노드가 없을 때 : 새 리프 노드를 생성하고 중간 노드를 첨가 (노드의 첨가, 삭제는 있으나 분열, 병합은 없음)
• 삭제
   - 노드와 원소들을 찾아서 Null 값으로 변경
   - 노드의 원소 값들이 모두 Null(공백 노드)인 경우에는 노드 삭제

---

B+트리

B-트리와 비슷하지만 인덱스를 사용하는 트리 (데이터베이스의 인덱스가 B+트리를 활용)

리프 노드는 연결리스트의 형태를 띠어 선형 검색이 가능

아주 작은 시간복잡도에서 검색 수행 가능, 키 값의 삭제는 리프 노드에서만 수행

 

B+트리의 노드 구조

• 모든 키 값과 데이터가 리프 노드에 모여 있음
• 모든 리프 노드가 연결리스트의 형태를 띠고 있음
• 리프 노드에서 선형 검사가 가능
• 리프 노드의 부모 키 값은 리프 노드의 첫 번째 키 값보다 작거나 같음

B+트리의 삽입

1. 분할이 일어나지 않을 때

• 삽입 위치가 리프 노드의 가장 앞 키 자리가 아니면 B-트리와 똑같은 삽입 과정을 수행
• 삽입 위치가 리프 노드의 가장 앞 키 자리인 경우 삽입 후 부모 키 값을 삽입된 키 값으로 갱신
• 그 후에 데이터를 넣어준다.

2. 분할이 일어날 때

• 분할이 일어나는 노드가 리프 노드라면 키를 부모 키로 올리지만 오른쪽 노드에 중간 키를 포함하여 분할
• 리프 노드는 연결리스트이므로 왼쪽, 오른쪽 자식 노드를 이어서 연결리스트 형태 유지
• 분할이 일어나는 노드가 리프 노드가 아니라면 기존 B-트리와 똑같이 분할을 진행
• 중간 키를 부모 키로 올리고 분할한 2개의 노드를 왼쪽, 오른쪽 자식으로 설정

B+트리의 삭제

B-트리와 유사, 삭제할 키는 무조건 리프 노드에 존재

 

1. 삭제할 키 값이 인덱스에는 없고 리프 노드의 처음 키가 아닌 경우

• 기존 B-트리 삭제 과정과 동일

2. 삭제할 키가 리프 노드의 처음 키인 경우

• 항상 키 값이 인덱스에도 존재한다.
• 먼저 리프 노드의 키를 삭제해야 한다.
• 그 노드의 키의 개수가 최소 키 개수라면 B-트리의 삭제처럼 형제 노드의 키를 빌려오거나 부모 노드의 키와 병합하는 과정을 수행
• 리프 노드가 병합할 때에 부모 키 값과 오른쪽 자식의 첫 번째 키 값이 동일하기 때문에 부모 키 값을 가져오는 과정은 생략하고 왼쪽 자식과 오른쪽 자식을 병합
• 리프 노드에서 이제 삭제를 진행하고 인덱스 내의 그 키 값을 inorder successor로 변경

B+트리의 성능

• 검색 : O( log n) 

트리에 저장된 키의 수 n에 대하여 B+트리의 높이 h = O( log n) 

디스크에서 각 노드를 읽기 위한 선형 탐색 성능은 상수 시간

• 삽입 : O( log n)
• 삭제 : O( log n)