SQL 데이터베이스(DB) B+ tree 인덱스, 복합 인덱스

B+ tree 인덱스

- 관계형 데이터베이스에서 가장 널리 사용되는 인덱스 구조

 

차수가 𝑛 인 B + tree

- 차수 : 한 노드(node)에서 하위 자식 노드(child node)를 가리키는 주소의 개수

- 중간 노드 구조

▪ 𝑃1 ~ 𝑃𝑛 : 자식 노드를 가리키는 포인터

▪ 𝐾𝑒𝑦1 ~ 𝐾𝑒𝑦𝑛−1 : 검색 키 (𝐾𝑒𝑦1 < 𝐾𝑒𝑦2 < ... < 𝐾𝑒𝑦𝑛−1)

▪ 𝑃𝑖+1 이 가리키는 하위 노드의 모든 검색 키는 𝐾𝑒𝑦𝑖 보다 크고 𝐾𝑒𝑦𝑖+1 보다 작거나 같음

 

B+ tree 특징

º 단말 노드에 레코드들의 주소 저장

º 루트 노드에서 단말 노드까지의 모든 경로의 길이는 같음

º 루트 노드는 최소 2개, 최대 n 개의 자식 노드를 가짐

º 루트 노드와 단말 노드를 제외한 중간 노드들은 최소 [n / 2], 최대 n개의 자식 노드를 가짐

 

B+ tree를 이용한 검색 방법

- 검색 키 값이 주어질 때, 루트 노드에서부터 그 키 값을 포함하는 첫 단말 노드까지 하나의 경로가 존재하고, 인덱스 노드에 포함된 키 값을 비교하면서 그 경로를 찾을 수 있음

- 단말 노드에 도달하면 검색 키를 포함한 레코드들에 대한 주소를 구할 수 있음 → 테이블 내의 레코드 접근

 

검색 성능

예) department 테이블에서 10000개의 레코드를 갖고, 이 중에서 dept_name 값이 '컴퓨터공학과'인 레코드를 검색할 때 인덱스가 없다면 최악의 경우 10000개의 레코드를 모두 검색해야함 , dept_name 필드에 차수가 10인 B+ tree 인덱스가 있다면!

 

• B+ tree의 높이 = [log10 10000] = 4
• 차수가 10, 검색 키 값의 수가 최대 10000개이므로, B+ tree의 높이는 최대 4를 넘지 않는다
• 최대 4개의 노드만 읽으며 원하는 레코드들을 찾을 수 있다

 

복합 인덱스

- 두 개 이상의 필드들에 대해 정의되는 인덱스

- 인덱스 엔트리들은 검색키 값의 순서대로 정렬됨

- 효율적인 검색을 위해 B+ tree 구성 가능

 

엔트리 정렬 방법

- 검색 키 값이 숫자인 경우 크기로 정렬 가능

- 검색 키 값이 문자열인 경우에는 사전식 순서에 따라 정렬

- 문자열, 숫자가 아닌 경우에는 엔트리들 간의 대소 관계 정의 필요

 

복합 인덱스의 효과

✔ 복합 인덱스가 정의된 필드들만을 이용하는 질의는 테이블 조회 없이 복합 인덱스 조회 만으로 처리 가능

 

주의사항

- 관련 필드의 순서에 따라 인덱스의 효과가 달라짐

 

예) (stu_id, class_id) 필드 순서에 효과적인 질의

select *
from takes
where stu_id = ‘1292001’ and class_id > ‘C101-01'

 

예) (class_id, stu_id) 필드 순서에 효과적인 질의

select *
from takes
where stu_id > ‘1292001’ and class_id = ‘C101-01’