[Database]Index에 대하여 + B-Tree

목차

 

Index

 

인덱스란 말 그대로 색인이다.

 

여기선 주어진 데이터베이스에서 원하는 자료를 빨리 찾을 수 있도록 도와주는 일종의 자료구조라 할 수 있다.

 

원하는 테이블의 컬럼(둘 이상도 가능하다)에 인덱스를 생성한다는 말은 데이터베이스 내부에서

 

해당 컬럼이 저장된 주소값을 가지는 자료구조를 테이블과 논리, 물리적으로 독립된 구조로 설계하는 것을 가리킨다.

 

이때 생성되는 인덱스는 컬럼의 값과 물리적 주소를 키/밸류로 가지는 구조를 가지며, 이를 이용해 빠른 탐색이 가능해진다.

 

참고로 인덱싱을 하지 않은 테이블의 경우, 원하는 값을 얻어내기 위해 모든 테이블을 스캔하는 Table Scan을 실행하며,

 

이는 최악의 경우 O(n)의 시간복잡도를 가지게 된다.

 

더 나가기 전에 장/단점과 인덱싱을 사용하기 좋은 환경에 대해 정리하고 넘어가자.

 

• 장점
  
  
  • 규모가 클수록 테이블 검색효율이 향상된다.
  • 보통은 인덱싱 과정에서 정렬도 이루어지기 때문에 최대/최소/정렬도 빠르게 수행한다.
  • 앞서 말한 테이블 스캔을 줄일 수 있기 때문에 시간뿐 아니라 시스템 리소스의 낭비도 줄일 수 있다.
  • 인덱스에 필요한 공간은 타겟 테이블에 비해 작다.
• 단점
  
  
  • 작다고 해도 인덱스를 위한 추가 공간이 필요하다.
  • 데이터의 삽입/수정/삭제가 빈번한 경우 성능이 저하된다.
    
    
    • 이는 인덱싱을 새로 해야하기 때문이며, 쿼리가 두 번 발생하는 효과가 있다.
    • 또한 삭제된 데이터의 인덱스를 제거하는 것이 아닌 '사용하지 않음'으로 남겨두기 때문에 덩치가 점점 커지게 된다.
  • 값의 범위가 적은 컬럼의 경우(성별, 연령대 등) 인덱스 조회 후 다시 많은 데이터를 스캔하기 때문에 효율이 떨어진다.

위 장단점을 바탕으로 인덱스를 사용하기 좋은 환경에 대해 정리하면 아래와 같다.

 

• 규모가 크면서 데이터의 중복이 적고 값의 범위가 넓은 테이블
• 삽입/수정/삭제보다 조회 쿼리(ORDER BY, JOIN 등을 포함)가 자주 발생하는 컬럼

계속해서 인덱스에서 사용하는 자료구조에 대해 살펴보자.

 

B-Tree

 

B-Tree는 이진 트리의 확장으로, 하나의 노드가 두 개 이상의 자식 노드를 가질 수 있는 트리를 말한다.

 

효율적인 탐색을 위해 모든 노드의 값은 정렬이 끝난 상태로 저장되며, Order를 나타내는 m 값을 갖는다.

 

계속해서 B-Tree of Order m은 아래와 같은 조건을 만족해야 한다.

 

• 각 노드가 가질 수 있는 자식 노드의 최대 개수는 m이다.
• 루트 노드는 최소한 두 개 이상의 자식 노드를 가진다.
• 루트 노드를 제외한 내부 노드는 적어도 [m/2] 개의 자식 노드를 가진다.
• X개의 자식 노드를 가진 내부 노드는 [X-1] 개의 값을 가진다.
• 모든 리프 노드의 높이는 같다.

이를 간단한 그림으로 나타내면 아래와 같다.

 

3차 B-Tree의 예시 그림이다. 푸른 색에는 노드의 값이, 붉은색에는 자식 노드를 향한 포인터가 배치되어 있다.

 

추가로 노드의 값이 정렬되어 있는 것도 확인할 수 있다.

 

위 조건에서 마지막 문장 덕분에 아래와 같은 최악의 상황은 벌어지지 않으며,

 

언제나 O(logN)의 시간복잡도가 보장된다.

 

Searching in B-Tree

 

이어서 B-Tree의 데이터 탐색 과정을 살펴보자.

 

이진 탐색 트리와 비슷하게, 아래와 같은 과정을 거쳐 데이터를 찾는다.

 

• 루트 노드부터 시작해서 값을 찾으면 탐색 종료
• 현재 노드의 값과 찾아야 하는 값을 비교해서 다음 노드 결정

예를 들어 위 그림에서 9를 찾는다고 할 때, 로직을 그림에 적용하면 다음과 같이 된다.

 

먼저, 구해야 하는 값이 4와 11 사이에 있으므로 가운데 포인터가 가리키는 곳을 탐색한다.

 

이번에는 8보다 큰 값을 탐색중이기 때문에 오른쪽 포인터가 가리키는 노드로 이동한다.

 

값을 발견하고 탐색 종료.

 

Insertion in B-Tree

 

계속해서 새로운 값이 삽입되는 알고리즘을 살펴보자.

 

B-Tree가 만족해야 하는 규칙 때문에, 새로운 값의 추가에 따라 트리 모양이 달라질 수 있다.

 

구체적으로 삽입의 과정은 다음과 같다.

 

• 비어있는 트리의 경우 루트 노드에 삽입. 루트 노드가 가득 찬 경우 노드를 분할하여 노드를 생성한다.
• 위의 검색 알고리즘을 이용해 값이 삽입될 위치를 찾는다.
• 해당 자리에 값을 삽입한 후 B-Tree의 규칙에 따라 노드를 분할한 후 부모 노드와 합치거나 새로운 노드를 생성한다.

 

조금 억지스럽지만 위 그림에 9.5가 삽입되는 경우를 가정해 보자.

 

검색 과정을 거쳐 9와 10 사이에 값을 삽입한다.

 

3개의 자식노드의 값은 두 개를 넘을 수 없으므로 중앙값을 기준으로 노드를 분할한다.

 

이어서 중앙값을 부모 노드와 합친뒤 비교한다. 역시 값이 넘치기 때문에 중앙값을 기준으로 노드를 분할한다.

 

중앙값인 8이 루트 노드에 합쳐진 것을 볼 수 있다.

 

루트 노드 역시 값이 꽉 차게 되므로 중앙값을 기준으로 분리한 뒤 새로운 노드를 생성한다.

 

정렬 종료.

 

Deletion in B-Tree

 

삭제의 경우엔 삽입보다 다소 복잡하다.

 

그래도 규칙을 지켜야 한다는 목표는 같기 때문에, 논리적으로는 그다지 어려울 것이 없다.

 

하나씩 천천히, 간단하게 알아보자.

 

Keys in Leaf nodes

 

삭제할 대상이 리프 노드에 있는 경우이다. 가장 간단한 경우 아래의 그림처럼

 

단순히 삭제해주면 된다. 이는 삭제할 값이 속한 노드의 값 개수가 최소보다 큰 경우에 속한다.

 

이어서 노드의 값 개수가 최소이면서 형제노드 값의 개수가 최소보다 큰 경우이다.

 

부모 노드가 리프 노드로 내려오고, 형제 노드가 분할되어 구조를 유지하는 것을 확인할 수 있다.

 

이어서 부모 노드의 키 개수가 최소보다 크며 형제 노드의 값 개수가 최소인 경우이다.

 

노드 삭제 후  부모 노드가 분할되어 자식 노드에 합쳐지는 것을 확인할 수 있다.

 

마지막으로 해당 노드와 형제, 부모 노드가 모두 최소 개수의 값을 가진 경우이다.

 

이 경우 트리구조가 다시 잡히게 된다.

 

규칙에 의해 노드가 합쳐지고 쪼개져 재구조화가 일어남을 확인할 수 있다.

 

Keys Not in Leaf nodes

 

리프 노드가 아닌 경우, 그중에서 현재 노드와 자식 노드의 값 개수가 최소보다 큰 경우는 아래와 같이 진행된다.

 

먼저 삭제할 값과 리프노드의 오른쪽 값 중 가장 큰 값, 혹은 왼쪽 값 중 가장 작은 값과 교체한다.

 

이후에는 리프 노드에서의 삭제와 동일하게 진행하면 된다.

 

이어서 현재 노드와 자식 노드의 값의 개수가 최소인 경우, 위에서 살펴본 리프노드의 마지막 경우인

 

해당 노드와 형제, 부모 노드가 모두 최소 개수의 값을 가진 경우와 동일하게 진행된다.

 

여기까지 살펴보면 진짜로 끝.

 

원래는 B+Tree까지 알아보고 글을 적으려고 했으나 살짝 지친 관계로 글을 분리해야겠다.

 

인덱스에 대한 소개 및 B-Tree 튜토리얼, 끝!

 

추가

인덱스의 자료구조로 O(1)의 시간복잡도를 가진 해시테이블이 채택되지 않는 이유는 해시 알고리즘 그 자체에 있다.

데이터의 아주 작은 부분만 달라져도 해시 값이 완전히 달라지기 때문에, 부등호 연산에 적합하지 않기 때문.