인덱스(Index)의 원리(B-Tree)편집자 확인

B-Tree는 데이터베이스와 파일 시스템에서 널리 사용되는 자기 균형 이진 탐색 트리의 일종이다. 모든 리프 노드가 같은 깊이를 유지하는 균형 잡힌 트리 구조로, 하나의 노드가 여러 개의 자식 노드를 가질 수 있다. 이는 디스크 접근 횟수를 최소화하여 대용량 데이터를 효율적으로 관리하기 위해 설계되었다.

B-Tree의 주요 특징은 다음과 같다. 첫째, 각 노드는 최소 m/2개(루트 노드 제외), 최대 m개의 자식 노드를 가질 수 있으며, 이를 트리의 차수(order)라고 부른다. 둘째, 노드 내에는 정렬된 키(key) 값이 저장되며, 키의 수는 자식 노드 수보다 하나 적다. 셋째, 모든 리프 노드는 동일한 레벨에 위치하여 트리의 균형을 보장한다. 이러한 구조 덕분에 탐색, 삽입, 삭제 연산의 시간 복잡도가 항상 O(log n)을 유지한다.

B-Tree는 특히 2차 저장장치에서의 성능을 중시한다. 디스크 I/O는 메모리 접근에 비해 매우 느리기 때문에, 하나의 노드(페이지)에 가능한 많은 키를 저장하여 트리의 높이를 낮추고 디스크 읽기 횟수를 줄이는 것이 핵심 목표이다. 이는 데이터베이스 관리 시스템의 인덱스 구현에 매우 적합한 특성이다.

B-Tree의 노드는 하나의 디스크 블록 또는 페이지 크기에 맞추어 설계되는 경우가 많습니다. 각 노드는 여러 개의 키와 자식 노드를 가리키는 포인터를 저장하는 컨테이너 역할을 합니다. 노드의 구조는 트리의 균형과 효율적인 검색을 보장하는 핵심입니다.

일반적인 m차 B-Tree에서, 각 노드는 다음 요소들을 포함합니다.

* 키(Key): 정렬된 순서로 저장된 실제 데이터 값 또는 데이터를 찾기 위한 값입니다.

* 자식 포인터(Child Pointer): 해당 키들 사이의 구간을 담당하는 자식 노드를 가리키는 포인터입니다. 리프 노드가 아닌 내부 노드에 존재합니다.

* 데이터 포인터(Data Pointer): 키에 해당하는 실제 데이터 레코드의 위치를 가리킵니다. B+Tree에서는 이 포인터가 리프 노드에만 집중됩니다.

각 노드가 가질 수 있는 키의 수는 엄격한 규칙에 의해 제한됩니다. 루트 노드를 제외한 모든 노드는 최소 ⌈m/2⌉ - 1개의 키를 가져야 하며, 최대 m-1개의 키를 가질 수 있습니다. 이 규칙은 노드가 너무 비어 있지 않도록 하여 공간 효율성을 유지하고, 특정 연산 후 발생하는 구조 재조정의 기준이 됩니다.

노드의 종류는 크게 세 가지로 구분됩니다.

1. 루트 노드(Root Node): 트리의 최상위 노드입니다. 자식이 없다면 리프 노드이기도 합니다.

2. 내부 노드(Internal Node): 루트와 리프 사이에 위치하며, 키와 자식 포인터만을 가집니다.

3. 리프 노드(Leaf Node): 트리의 가장 말단에 위치하며, 모든 키와 대응하는 데이터 포인터를 저장합니다. 모든 리프 노드는 연결 리스트처럼 서로 연결되어 순차 접근을 가능하게 합니다[2].

이러한 노드 구조 덕분에 B-Tree는 한 번의 디스크 접근으로 많은 키를 메모리로 읽어올 수 있으며, 트리의 높이를 로그 수준으로 낮게 유지할 수 있습니다.

B-Tree에서 검색은 루트 노드에서 시작하여 리프 노드까지 내려가는 과정이다. 검색 알고리즘은 각 노드 내에서 이진 탐색 또는 순차 탐색을 수행하여 목표 키를 찾거나, 다음으로 탐색할 자식 노드를 결정한다.

구체적인 과정은 다음과 같다. 먼저 루트 노드에서 시작하여, 노드 내에 저장된 키 값들을 순서대로 검사한다. 찾고자 하는 키 K가 현재 노드에 존재하면 검색은 성공적으로 종료된다. 키가 존재하지 않으면, K가 위치해야 할 구간을 찾아 해당 구간에 대응하는 자식 노드 포인터를 따라 내려간다. 예를 들어, 노드에 키 [10, 20, 30]이 있고 K=25라면, 20과 30 사이의 구간에 속하므로 20과 30 사이의 포인터가 가리키는 자식 노드로 이동한다. 이 과정은 키를 찾거나 리프 노드에 도달할 때까지 재귀적으로 반복된다.

검색의 효율성은 트리의 높이에 직접적으로 의존한다. B-Tree는 모든 리프 노드가 같은 깊이를 유지하는 균형 트리이므로, 최악의 경우에도 루트에서 리프까지의 경로 길이는 O(log n)이다. 여기서 n은 트리에 저장된 총 키의 수이다. 각 노드 내 탐색은 일반적으로 메모리 내에서 빠르게 이루어지므로, 디스크 I/O 횟수(즉, 접근하는 노드 수)가 성능의 주요 지표가 된다. B-Tree는 노드 하나가 디스크의 한 블록 크기에 맞도록 설계되어, 한 번의 디스크 읽기로 많은 키를 비교할 수 있어 효율적이다[4].

삽입 연산은 항상 단말 노드에서 시작된다. 먼저 검색 과정을 통해 새로운 키가 들어가야 할 적절한 단말 노드를 찾는다. 해당 노드에 여유 공간이 있다면, 키 값을 올바른 순서로 삽입하여 연산을 종료한다.

노드가 이미 최대 키 수(차수)에 도달해 여유 공간이 없는 경우, 노드 분할이 발생한다. 분할 과정은 다음과 같다.

1. 가득 찬 노드의 키들을 정렬된 상태로 유지하며 중간값(median) 키를 선택한다.

2. 중간값 키는 부모 노드로 승격된다.

3. 중간값을 기준으로 나머지 키들은 두 개의 새로운 형제 노드로 분할된다.

4. 승격된 중간값 키를 부모 노드에 삽입한다. 이때 부모 노드도 가득 찼다면, 동일한 분할 과정이 재귀적으로 상위 노드로 전파된다. 최악의 경우 루트 노드까지 분할이 진행되어 트리의 높이가 증가할 수 있다.

분할로 인해 트리는 항상 균형을 유지한다. 모든 단말 노드는 루트로부터 동일한 깊이를 가지며, 각 노드의 키 수는 최소 차수에 의해 정의된 하한을 만족한다. 이 과정은 아래 표와 같이 요약할 수 있다.

B-Tree에서 삭제 연산은 항상 리프 노드에서 시작됩니다. 삭제할 키가 내부 노드에 있는 경우, 해당 키의 직전 원소나 직후 원소(둘 다 리프 노드에 있음)와 위치를 교환하여 문제를 리프 노드에서의 삭제로 귀결시킵니다. 이후 리프 노드에서 키를 제거합니다.

삭제 후 노드의 키 개수가 최소 개수 미만으로 떨어지면 트리의 균형을 맞추기 위한 작업이 필요합니다. 먼저, 형제 노드에게 키를 빌려올 수 있는지 확인합니다. 즉, 인접한 형제 노드 중 키를 하나 내놓은 후에도 최소 개수를 유지할 수 있는 노드가 있는지 살핍니다. 가능하다면, 부모 노드의 분기 키를 통해 키를 재분배하고 부모 키를 조정합니다. 이 과정을 재배치(redistribution)라고 합니다.

모든 형제 노드도 최소 개수의 키만 가지고 있어 키를 빌려줄 수 없다면, 노드 병합(merge) 연산을 수행합니다. 현재 노드와 형제 노드 하나, 그리고 두 노드를 구분하던 부모 노드의 키를 합쳐 하나의 노드로 만듭니다. 이로 인해 부모 노드의 키가 하나 줄어들어, 부모 노드에서도 키 개수가 최소 미만이 될 수 있습니다. 이 경우 부모 노드에서부터 루트 방향으로 동일한 재배치 또는 병합 과정이 재귀적으로 반복되어 트리의 균형을 유지합니다.

병합 연산은 트리의 높이가 감소할 수 있는 유일한 연산입니다. 루트 노드가 키를 하나만 가지고 있었고, 두 자식 노드가 병합되면 새로운 노드가 루트가 되어 트리의 높이가 1 줄어듭니다. 이러한 삭제와 재균형 과정은 트리의 모든 리프 노드가 동일한 깊이를 유지하도록 보장합니다.

B+Tree는 B-Tree의 변형으로, 모든 실제 데이터 레코드에 대한 키(key)가 리프 노드에만 저장되고, 내부 노드는 단순히 검색을 위한 인덱스 역할만 수행하는 트리 구조이다. 리프 노드들은 서로 연결 리스트로 연결되어 있어 범위 검색이나 순차 접근이 매우 효율적이다.

B+Tree의 주요 특징은 다음과 같다. 첫째, 내부 노드(인덱스 노드)는 키와 자식 노드를 가리키는 포인터만을 가지며, 실제 데이터는 저장하지 않는다. 둘째, 모든 리프 노드는 같은 깊이에 위치하여 균형을 유지한다. 셋째, 리프 노드는 키와 해당 키에 대응하는 실제 데이터의 위치(포인터)를 저장하며, 형제 노드들끼리 양방향 연결 리스트로 연결되어 있다. 이 구조 덕분에 특정 키를 찾는 검색뿐만 아니라, 'A부터 B까지'와 같은 범위 질의를 처리할 때 매우 빠르게 수행할 수 있다.

이러한 설계로 인해 B+Tree는 특히 데이터베이스 관리 시스템(DBMS)과 파일 시스템의 인덱스 구조로 널리 채택되었다. 데이터베이스에서 풀 테이블 스캔(full table scan) 없이 인덱스만 순회하며 데이터를 접근할 수 있고, 디스크 I/O를 최소화하면서도 안정적인 성능을 제공한다. 또한, 내부 노드가 데이터를 저장하지 않으므로 더 많은 키를 수용할 수 있어 트리의 높이가 낮아지고, 이는 검색 성능 향상으로 이어진다.

B*Tree는 B-Tree의 변형 중 하나로, 노드의 공간 활용도를 높이고 분할 빈도를 줄이기 위해 설계된 자료 구조이다. 이 구조는 1979년 도널드 커누스가 *The Art of Computer Programming*에서 처음 언급했다[6].

B*Tree의 핵심 아이디어는 노드가 가득 찼을 때 즉시 분할하지 않고, 형제 노드로 키를 재분배하는 것이다. 구체적인 규칙은 다음과 같다.

1. 삽입 시 대상 노드가 가득 차면, 먼저 좌우 형제 노드에 빈 공간이 있는지 확인한다.

2. 빈 공간이 있는 형제 노드가 있다면, 현재 노드의 일부 키를 그 형제 노드로 이동시켜 공간을 확보한다. 이 과정을 키 재분배(redistribution)라고 한다.

3. 인접한 두 형제 노드 모두 가득 찬 경우에만, 이 두 노드와 그 사이의 부모 키를 합쳐 세 개의 노드를 두 개의 노드로 분할(split)한다. 이는 기존 B-Tree의 2-way 분할(한 노드를 두 노드로 나눔)과 차별화된다.

이 방식은 노드의 평균 저장 밀도를 약 2/3에서 3/4 수준으로 높이는 효과가 있다. 결과적으로 트리의 높이가 낮아지고, 디스크 I/O 횟수가 감소하여 검색 성능이 향상될 수 있다.

그러나 구현 복잡도가 상대적으로 높고, 키 재분배를 위해 형제 노드를 항상 확인해야 하므로 연산 오버헤드가 존재한다. 이러한 이유로 B*Tree는 이론적으로 우수한 성능을 보이지만, 실제 데이터베이스 관리 시스템(DBMS)에서는 구현의 간결성과 효율성 사이의 균형을 고려한 B+Tree가 더 널리 채용된다.

클러스터드 인덱스는 테이블의 물리적 행 저장 순서를 인덱스 키 값의 순서와 일치시키는 구조이다. 하나의 테이블에 오직 하나만 생성할 수 있으며, 주로 기본 키를 기준으로 생성된다. 데이터 자체가 인덱스이기 때문에 검색 속도가 매우 빠르지만, 새로운 데이터를 삽입할 때 물리적 위치를 재배치해야 하므로 삽입 및 갱신 비용이 높은 편이다. 대부분의 관계형 데이터베이스 관리 시스템에서 테이블당 하나의 클러스터드 인덱스를 허용한다.

반면, 넌클러스터드 인덱스는 데이터의 물리적 순서와 독립적으로 생성되는 인덱스 구조이다. 하나의 테이블에 여러 개를 생성할 수 있으며, 인덱스의 리프 노드는 실제 데이터 행이 저장된 위치를 가리키는 포인터를 포함한다. 이 포인터는 일반적으로 페이지 ID와 행 번호 또는 클러스터드 인덱스 키 값이다. 따라서 넌클러스터드 인덱스를 통해 데이터를 찾으려면 인덱스 검색 후 추가적으로 데이터 페이지를 접근해야 하는 랜덤 액세스가 발생한다.

두 인덱스의 주요 차이점을 비교하면 다음과 같다.

데이터베이스 설계 시, 범위 질의가 빈번한 컬럼에는 클러스터드 인덱스를, 다양한 조건으로 조회가 필요한 컬럼에는 넌클러스터드 인덱스를 적용하는 것이 일반적이다. SQL Server와 MySQL의 InnoDB 스토리지 엔진은 클러스터드 인덱스를 기본으로 사용하는 반면, Oracle Database는 인덱스 구성 테이블이라는 유사한 개념을 제공한다.

인덱스 성능은 디스크 I/O 횟수, 트리의 높이, 페이지 채우기 비율 등 여러 요소에 의해 결정된다. 데이터베이스 시스템은 디스크 접근 속도가 메모리 접근보다 훨씬 느리기 때문에, 성능 최적화의 핵심은 필요한 디스크 읽기/쓰기 횟수를 최소화하는 데 있다.

B-Tree의 높이는 성능에 직접적인 영향을 미친다. 트리의 높이가 증가하면 루트 노드부터 리프 노드까지 탐색해야 하는 경로가 길어져, 최악의 경우 더 많은 디스크 블록을 읽어야 한다. 트리의 높이는 일반적으로 O(log_m N)으로, 여기서 m은 노드의 최대 자식 수이고 N은 키의 총 개수이다. 따라서 높은 차수(m)를 가지는 B-Tree는 더 낮은 높이를 유지하여 검색 효율을 높일 수 있다. 노드의 채우기 비율(Fill Factor)도 중요한 요소이다. 노드가 데이터로 꽉 차 있으면 트리의 높이는 최소화되지만, 새로운 키 삽입 시 빈번한 노드 분할이 발생하여 성능 저하를 초래할 수 있다. 반대로 채우기 비율이 너무 낮으면 트리의 높이가 불필요하게 증가하고, 디스크 공간 활용도가 떨어진다. 대부분의 데이터베이스 시스템은 삽입 성능과 공간 활용도를 고려하여 적절한 채우기 비율 임계값(예: 70%)을 설정하여 운영한다.

데이터 접근 패턴도 인덱스 성능을 좌우한다. 순차 접근이 빈번한 경우, B+Tree와 같이 모든 데이터가 리프 노드에 연결된 구조가 유리하다. 반면, 랜덤 접근이 주를 이루는 경우 트리 높이 자체가 더 결정적인 요소가 된다. 또한, 인덱스 조각화가 발생하면 논리적으로 연속된 데이터가 물리적으로 흩어져 저장되어, 순차 스캔 시 추가적인 디스크 탐색 시간이 발생할 수 있다. 주기적인 인덱스 재구성(REORGANIZE) 또는 재생성(REBUILD) 작업은 이러한 조각화를 해소하고 성능을 회복시키는 일반적인 방법이다.

해시 테이블은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 고정된 크기의 해시 값으로 변환한다. 이 해시 값을 배열의 인덱스로 사용하여 해당 키에 대응하는 값을 저장하거나 검색한다. 이론적으로 평균 시간 복잡도가 O(1)에 달하는 매우 빠른 검색 성능이 주요 특징이다.

그러나 해시 테이블은 해시 충돌이라는 문제를 안고 있다. 서로 다른 키가 동일한 해시 값으로 매핑될 경우 발생하며, 이를 해결하기 위해 체이닝이나 개방 주소법 등의 기법이 사용된다. 또한, 해시 테이블은 일반적으로 범위 검색이나 순차 접근을 효율적으로 지원하지 않는다. 키의 순서를 보장하지 않으며, 'A'부터 'Z'로 시작하는 모든 레코드를 찾는 것과 같은 쿼리에 부적합하다.

따라서 데이터베이스 시스템에서는 범위 질의가 빈번한 경우 B-Tree나 그 변형이 선호되는 반면, 정확한 키 매칭만 필요한 경우나 인메모리 데이터베이스에서는 해시 테이블이 유리한 선택지가 될 수 있다.

레드-블랙 트리는 균형 이진 탐색 트리의 한 종류로, 각 노드에 '레드' 또는 '블랙' 색상을 부여하여 트리의 균형을 유지합니다. 이 트리는 삽입, 삭제, 검색 연산 모두 최악의 경우에도 O(log n)의 시간 복잡도를 보장합니다. B-Tree가 주로 디스크 기반의 대용량 데이터 관리에 최적화된 반면, 레드-블랙 트리는 주로 메모리 내에서 효율적인 연산이 필요한 경우에 널리 사용됩니다.

레드-블랙 트리는 다음 다섯 가지 규칙을 만족해야 합니다.

1. 모든 노드는 레드 또는 블랙이다.

2. 루트 노드는 블랙이다.

3. 모든 리프 노드(NIL 노드)는 블랙이다.

4. 레드 노드의 자식 노드는 모두 블랙이다(레드 노드는 연속될 수 없다).

5. 각 노드에서부터 그 노드의 자손 리프 노드까지의 모든 경로에는 동일한 개수의 블랙 노드가 존재한다.

삽입 또는 삭제 연산 후 이러한 규칙이 깨질 수 있으며, 트리는 회전(rotation)과 노드의 색상 재조정을 통해 규칙을 다시 만족하도록 수정됩니다. 이 과정은 로그 시간 내에 완료됩니다.

레드-블랙 트리와 B-Tree는 서로 다른 장단점을 가집니다. 레드-블랙 트리는 일반적으로 B-Tree보다 더 많은 회전 연산이 필요하며, 노드당 하나의 키만 저장합니다. 이는 메모리에서의 탐색 효율성은 높일 수 있지만, 디스크 I/O를 최소화해야 하는 데이터베이스 시스템에서는 B-Tree나 B+Tree가 더 적합한 선택이 됩니다. 많은 프로그래밍 언어의 표준 라이브러리(예: C++ STL의 std::map, Java의 TreeMap)에서 내부적으로 레드-블랙 트리를 구현하여 사용하고 있습니다.