인덱스(B-Tree, B+Tree)

데이터베이스의 성능을 향상시키기 위해서는 디스크 I/O를 줄이는 것이 가장 중요하다. 디스크 I/O란 데이터를 읽고 쓰는 작업으로, 데이터를 작성하거나 수정할 때 디스크에 저장되는 과정을 의미한다. 디스크 접근은 시간이 많이 걸리기 때문에 디스크 I/O를 최소화하는 것이 데이터베이스 성능을 높이는 핵심이다.

 

인덱스를 활용하면 데이터를 더 빠르게 조회할 수 있어 디스크 I/O를 줄이는 데 효과적이다.

인덱스는 데이터베이스가 테이블의 모든 데이터를 탐색하지 않고도 원하는 정보를 빠르게 찾을 수 있도록 설계되어 있다. 이를 통해 불필요한 디스크 I/O 작업을 줄이고 빠르게 조회할 수 있다.

 

인덱스란?

간단히 말해 인덱스는 책의 목차와 비슷한 개념이다. 책의 내용을 "데이터"라고 하고, 페이지 번호를 "인덱스"라고 생각해 보자. 우리가 특정 내용을 찾기 위해 책의 모든 페이지를 일일이 읽지 않는 것처럼, 데이터베이스도 인덱스를 사용해 필요한 데이터만 빠르게 찾을 수 있다.

 

B-Tree, B+Tree

B-Tree와 B+Tree는 효율적인 인덱싱을 위해 널리 사용되는 자료구조다.
이러한 구조들은 대량의 데이터를 신속하게 검색하고, 삽입 및 삭제 시 성능 저하를 방지하는 데에 중점을 두고 있다.

 

B-Tree

B-Tree는 널리 쓰이는 인덱스 자료구조 중 하나로 이진 트리를 확장한 균형 트리 형태이다.
한 노드당 자식 노드가 2개 이상 가능하다.

 

구성 요소는 아래와 같다.

• Root 노드: 트리의 최상위 노드
• Branch 노드: 중간 노드(내부 노드), key와 데이터를 담을 수 있다.
• Leaf 노드: 최하위 노드, key와 데이터를 담을 수 있다.

(여기서 말하는 데이터는 실제 DB상 데이터가 아니라 자료구조상 value를 말한다.)

 

 

이진트리를 확장한 B-Tree

이진트리(Binary Tree)는 최대 2개의 자식 노드를 가지는 트리를 말한다.

맨 위의 노드를 루트(root) 노드라고 하고, 각 노드는 왼쪽 자식(left child) 노드와 오른쪽 자식(right child) 노드를 가질 수 있다.
각 노드의 왼쪽에는 해당 노드보다 작은 값의 노드들, 오른쪽에는 큰 값의 노드들이 위치하도록 정렬한 이진트리를 이진 탐색 트리(Binary Search Tree)라고 한다.

 

이진 탐색 트리는 자료가 많아질수록 트리의 높이(height)가 커지기 때문에 검색에 불리하고 좌우 불균형이 일어난다.

이렇게 이진 탐색트리가 한쪽으로 치우쳐진 skewed binary search tree(편향 이진 탐색 트리)가 되면 최악의 경우 O(n)의 시간복잡도를 가지게 된다.

B-Tree는 이러한 문제를 해결하기 위해 트리의 높이를 줄이고, 데이터를 균형 있게 분산시켜 검색 속도를 일정하게 유지한다.
보다 자세한 검색, 삽입, 삭제 과정은이 블로그에 아주 잘 설명되어 있다.

 

B+Tree

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.

B-Tree는 모든 노드(internal node + leaf node)의 key마다 데이터가 있었다면 B+Tree는 오직 리프 노드에만 key와 데이터를 저장할 수 있다.(브랜치 노드에는 key만 포함된다.)

 

또한 모든 리프 노드들은 링크드 리스트 형태로 연결되어 있어 인접한 다음 노드에 바로 접근할 수 있으므로 범위 검색에 효율적이다.

 

 

B-Tree vs B+Tree

 

1. 검색 방법

• 데이터를 검색할 때 항상 리프 노드까지 이동하므로 검색 경로가 단순해진다.
• B-Tree: 모든 노드(internal node + leaf node)에 키와 값이 함께 저장
• B+Tree: internal 노드에는 키만 저장, 리프 노드에는 `키와 값`이 저장된다.

 

2. 포인터의 사용

• 데이터를 찾기 위해 internal 노드를 항상 통과해야 조회한다. ⇒ 추가적인 단계 필요 (단점)
• internal 노드를 통하지 않고도 형제 노드로 이동 가능하고, 범위 검색이나 범위 쿼리가 쉽다.
• B-Tree: internal 노드의 포인터를 통해서만 리프 노드로 이동 가능
• B+Tree: 리프 노드끼리 서로 연결 리스트로 연결되어 있다.

 

3. 범위 쿼리와 범위 검색

• B-Tree: 범위 쿼리를 수행하려면 트리의 루트에서부터 리프 노드까지 이동하면서, 루트 노드, internal 노드에 있는 데이터까지 함께 조회해야 한다.
• B+Tree: 데이터는 리프 노드에만 존재하므로, 범위 쿼리는 리프 노드를 시작으로 연결된 리스트를 따라가면 모든 데이터를 조회할 수 있다.

 

4. 순차 탐색 및 정렬

• B-Tree: 순차적인 탐색이나 정렬을 위한 추가적인 알고리즘이 필요해서 (예. inorder traversal) B+Tree보다 더 복잡하다.
• B+Tree: 연결된 리스트를 따라가면서 순차 탐색이 용이하며, 키들은 항상 정렬된 상태를 유지하면서 저장된다.

 

5. 메모리 사용

• B-Tree: 리프 노드와 내부 노드가 각각 데이터와 포인터까지 가지고 있기 때문에 B+Tree보다 더 많은 메모리 공간을 차지한다.
• B+Tree: 데이터는 리프 노드에만 저장되고, internal 노드는 키만 갖고 있으면 되므로, 메모리 효율이 좋다.

 

해시 테이블(Hash Table)

Hash 인덱스

해시 인덱스는 key-value 쌍으로 데이터를 저장하는 해시 테이블 자료구조로이다.
특정 컬럼에 대해 Hash 인덱스를 설정할 경우, 해당 컬럼의 값에 해시 함수를 적용하여 해쉬 값을 얻고, 이 해쉬 값의 위치에 컬럼 원본 값과 레코드 주소가 저장된다.

 

한계

Hash 인덱스는 검색 속도가 O(1)로 매우 빠르다.
하지만 각 key를 독립적인 위치에 매핑하기 때문에 '단 하나의 데이터를 탐색할 때' 해당되는 이야기다.
키의 순서를 정렬하지 않기 때문에 등호 연산(=)에만 최적화되어 있어, 비교 연산(<, >)에는 적합하지 않다.

 

SELECT 문에서 = 연산이 자주 사용될 경우 해시 인덱스를 사용하면 매우 빠른 검색이 가능하다. 하지만 범위 검색에는 위의 이유로 B+Tree가 더 적합하다.

 

 

인덱스를 잘 설정하는 방법

인덱스는 데이터베이스에서 검색 및 처리 속도를 크게 향상시키지만, 부적절하게 설정하면 성능 저하와 저장 공간 낭비로 이어질 수 있다. 인덱스를 생성할 때는 오랜 시간이 소요될 수 있을 뿐만 아니라 저장 공간이 추가로 필요하다. 따라서 적절한 인덱스 선택이 매우 중요하다.

 

1. 중복 데이터에 인덱스를 피하자

인덱스는 데이터 검색을 빠르게 만들지만, 중복이 많은 데이터에 인덱스를 생성하면 원하는 결과를 찾기 위해 추가적인 디스크 I/O가 발생할 가능성이 크기 때문에 오히려 검색 속도를 저하시킬 수 있다.

 

주민등록번호와 성별 중 어떤 컬럼에 인덱스를 추가하는 것이 좋을까?
주민등록번호 컬럼에 인덱스를 추가하는 것이 더 효과적이다. 주민등록번호는 고유한 값이 많아 효율적인 검색이 가능하지만, 성별은 '남'과 '여'처럼 값이 중복되기 때문에 인덱스의 효율성이 떨어진다.

 

2. Primary Index와 Secondary Index의 차이를 이해하고 설정하자

Primary Index(클러스터드 인덱스)

클러스터드 인덱스는 기본키(Primary Key)를 기반으로 생성되는 인덱스를 말한다.
데이터가 물리적으로 정렬된 방식으로 저장되기 때문에, 특정 범위의 데이터를 검색할 때 매우 효율적이다
테이블당 하나만 생성할 수 있기 때문에 신중하게 선택해야 한다.

 

Secondary Index(비클러스터드 인덱스)

기본키(primary key)나 Primary Index 외에 추가로 생성된 인덱스를 말한다.
데이터가 물리적으로 정렬되지는 않지만 검색 속도를 높이는 데 도움을 준다.

특정 컬럼에 Secondary Index를 추가하면, 데이터베이스가 테이블을 전체 검색하는 대신 인덱스를 사용해 데이터를 빠르게 찾을 수 있다.
예를 들어, SELECT 문에서 자주 사용되는 컬럼에 설정하면 검색 속도가 크게 향상된다.

 

3. 결합 인덱스(Composite Index)를 설정할 땐 순서가 중요하다

결합 인덱스는 두 개 이상의 컬럼을 합쳐 하나의 인덱스로 생성하는 방식이다.
AND 조건으로 검색할 때 매우 유리하지만, OR 조건에는 인덱스를 두 개의 독립적인 검색 경로로 나누기 때문에 FULL SCAN할 가능성이 높아지므로 효율적이지 않다.

 

예를 들어 아래의 두 인덱스는 같은 컬럼을 포함하지만 처리 방식이 다르다.

CREATE INDEX idx_emp_comp ON emp(title, author);
CREATE INDEX idx_emp_comp ON emp(author, title);

인덱스는 첫 번째 컬럼을 기준으로 데이터를 정렬하고 탐색한다.

CREATE INDEX idx_emp_comp ON emp(title, author);는 title을 우선 기준으로 정렬한 후, title의 값이 같은 경우에만 author를 기준으로 정렬한다.

SELECT title, author 과 SELECT title 에서는 적합하지만 SELECT author 만을 검색하는 경우, 이 인덱스는 효과적으로 작동하지 않는다.

 

따라서 SELECT 문에서 어떤 컬럼이 더 자주 사용되는지를 분석한 후, 자주 사용되는 컬럼을 인덱스의 첫 번째 위치에 설정하는 것이 좋다.

 

 

 

 

 

참고
데이터베이스 인덱스(index) 개념 정리
Balanced Binary Search Tree(균형 이진탐색 트리)
인덱스에서 B+Tree를 사용하는 이유
11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등
# DB의 인덱스와 B-tree, B+tree
# B+Tree: 개념, 특징, B-Tree와의 차이점 정리
B트리 인덱스와 Hash 인덱스