B-tree가 데이터베이스 인덱스에 사용되는 이유

대부분의 DBMS는 데이터를 2차저장소에 저장하고 관리한다. 2차저장소는 컴퓨터 구성요소에서 보조기억장치를 말한다. (ex: 하드디스크) 2차저장소는 다음과 같은 특징이 있다. 

 

 

1. 데이터를 처리하는 속도가 컴퓨터 시스템에서 가장 느림
2. 데이터를 저장하는 용량이 가장 큼

 

그럼 왜 데이터를 2차저장소에 저장하는 걸까? 여러 이유가 있겠지만 2개를 뽑자면 아래와 같다.

 

 

1. 서비스를 운영하면서 중요한 데이터들을 영구적으로 보관할 저장소가 필요
2. 서비스가 커지면서 많은 양의 데이터를 보관할 장소가 필요

 

이러한 이유로 처리하는 속도는 느리지만 데이터를 보관할 장소로 쓰인다. 2차저장소의 특징은 한가지가 더 있는데, 데이터를 읽고 쓸 때 block(또는 페이지) 단위로 실행이 된다. block이란 2차저장소에서 데이터를 읽고 쓰는 논리적 단위다. 예를 들어서 2차저장소에 A값을 저장하고 A값을 읽어오고 싶다면 A값을 포함하고 있는 하나의 block을 가져온다. 

 

 

읽을때 A의 값만 읽는것이 아닌 A를 포함하고 있는 하나의 block(점선표시영역)을 읽는다.

 

 

block안에는 A값 말고도 다른값들도 있는데, 한꺼번에 꺼내온다.

왜 원하는 값만 꺼내지 않고 block단위로 꺼내는걸까?

 

 

2차저장소는 데이터를 처리하는 속도가 느린데, 만약 원하는 값을 읽고싶을 때마다 2차저장소에 값을 꺼내온다면 2차저장소에 접근할때마다 비용이 드는 것이다. 따라서 block단위로 데이터를 한번에 가져와서 메모리에 올려두고 만약 필요한 값이 메모리에 이미 있다면  바로 사용할 수 있기 때문에 효율적이다. 

 

 

하지만 만약 A값이 필요해서 하나의 block을 꺼내왔는데 다른값은 사용되지 않는다면? 메모리에 올려두기 때문에 메모리용량만 차지하게 된다. 따라서 연관이 있는 데이터들을 block단위로 뭉쳐놓는게 좋다. (참조의 지역성이라고, 전산 이론중 하나로 한번 참조한 데이터는 다시 참조될 가능성이 높고 해당 데이터와 관련된 데이터들도 같이 참조될 가능성이 높다는 이론이 있다. 하나의 block안에 서로 관련된 데이터들을 저장한다면 저장공간 활용도가 올라간다.)

 

 

여기까지 DB의 데이터가 2차저장소에 저장되고 관리된다는 것을 이야기했다. 2차저장소에 저장된 데이터를 빠르게 탐색하고 효율적으로 삽입, 삭제를 하기 위해서는 적절한 자료구조를 사용해야 하는데, 이때 B-tree기반의 구조가 데이터베이스에서 인덱싱을 통해 빠른 탐색을 할 때의 자료구조로 사용하기에 적합하다. 그럼 다른 자료구조는 데이터베이스 인덱스의 자료구조로 사용하기에 적합하지 않을까? 분명하게 B-tree보다 탐색이 빠른 자료구조가 존재할텐데 왜 데이터베이스 인덱스로 B-tree가 선택된걸까? 한번 알아보자.

 

 

먼저 B-tree를 간단하게 알아보겠다. B-tree구조로 5, 9, 3, 2, 4, 1, 30 데이터를 넣는다고 하면 아래와 같이 저장된다. 

 

 

 

 

B-tree가 일반트리와 다른 점, 즉 특징은 다음과 같다.

 

 

1. 하나의 노드에 여러 데이터를 저장할 수 있다 (이 때 데이터들은 오름차순으로 정렬된다)
2. 하나의 노드는 여러 자식노드를 가질 수 있다

 

 

한 노드가 가질 수 있는 자식노드의 개수를 차수라고 하는데, 차수에 따라서 한 노드에 저장할 수 있는 데이터의 수가 정해진다. 위 사진의 B-tree는 각 노드가 3개의 자식노드를 가질 수 있기 때문에 한 노드에서 최대로 저장할 수 있는 데이터의 수는 차수 - 1 = 2개다.

이러한 B-tree의 구조적 특징이 데이터를 탐색할 때 어떤 이점을 가지는지 알아보겠다. 

 

 

트리 종류 중 하나인 이진탐색트리와 비교해보겠다. 위에 예시를 들었던 5, 9, 3, 2, 4, 1, 30 데이터를 B-tree구조와 이진탐색트리 구조로 넣는다고 하면 아래와 같이 저장된다.

 

 

왼쪽은 B-tree, 오른쪽은 이진탐색트리 구조다

 

 

이제 데이터 1을 찾는다고 했을 때, 두 구조는 어떻게 탐색을 할까? B-tree부터 보자. 

먼저 루트노드의 데이터에서 1과 3을 비교한다. 1은 3보다 작기 때문에 첫번째 자식노드로 접근한다. 자식노드의 데이터에서 1과 1을 비교하여 데이터를 찾았다.

 

 

데이터 1을 탐색하는 과정

 

 

과정을 보면 총 한번의 노드접근이 일어나는 것을 알 수 있다. 이제 이진탐색트리구조에서 데이터 1을 찾아보자. 먼저 루트노드의 5와 비교한다. 1은 5보다 작기 때문에 왼쪽 자식노드로 접근한다. 왼쪽 자식노드의 3과 1을 비교한다. 1은 3보다 작기 때문에 왼쪽 자식노드로 접근한다. 2와 1을 비교한다. 1은 2보다 작기 때문에 왼쪽 자식노드로 이동한다. 1과 1을 비교하여 데이터를 찾았다.

 

 

데이터 1을 탐색하는 과정

 

 

위 사진을 봤을때 총 3번의 노드접근이 일어나는 것을 알 수 있다. 1번 접근과 3번 접근을 비교해봤을 때 1번만 접근하여 데이터를 찾는게 속도가 더 빠르다. 각 노드가 2차저장소에서 하나의 block이라고 한다면, 노드의 접근 한번한번이 데이터 조회 성능을 느리게 만든다.

 

 

왜 B-tree가 1번의 접근만으로 데이터를 찾을 수 있었던 걸까? B-tree는 이진탐색트리와 다르게 하나의 노드가 여러개의 자식노드를 가질 수 있기 때문이다. 이진탐색트리는 왼쪽, 오른쪽으로 접근할지 정해서 2분의 1씩 범위를 좁히는 반면, B-tree는 자식노드의 개수(N)에 따라 N분의 1씩 범위를 더 빠르게 좁힐 수 있다. 

 

 

이 점을 극대화해서 생각해볼 수 있다. 

만약 각 노드가 가질 수 있는 자식노드의 개수가 101개라고 한다면? 아래 사진은 차수가 101이고 각 노드에 저장할 수 있는 데이터의 개수가 100개라고 했을 때의 구조다.

 

 

출처: 쉬운코드

 

 

위 사진의 구조에서는 총 몇개의 데이터를 저장할 수 있을까? 계산해보면 약 1억개의 데이터를 높이가 3인 트리구조에 저장할 수가 있다. 더 대단한 점은 1억개의 데이터에서 특정값을 찾을 때 단 3번의 접근만으로 찾을 수 있다. 데이터의 개수가 수백만, 수천만개, 억단위까지 많아져도 구조를 유지하면서 데이터를 저장할 수 있다는 장점과, 방대한 데이터에서도 특정값을 찾을 때 몇번의 접근만으로 탐색이 가능한 장점은 데이터베이스의 인덱스로 사용하기에 적합하다. 

 

 

또 다른 이점은 각 노드가 저장할 수 있는 데이터의 수에 있다. B-tree는 한 노드에 여러 데이터를 저장할 수 있다. 이진탐색트리는 한 노드에 하나의 데이터만 저장할 수 있다. 만약 각 노드가 하나의 block이라고 했을 때, 이진탐색트리에서 자식노드를 읽어올 때 자식노드에 저장된 데이터를 포함한 하나의 block을 읽어온다. 즉 탐색에 필요한 데이터 이외의 데이터들을 같이 읽어오기 때문에 저장공간에 대한 활용을 제대로 못하고 있다고 할 수 있다. 반면 B-tree는 한 노드에 여러 데이터를 저장할 수 있기 때문에, 하나의 block을 읽어와도 읽어온 데이터들 대부분이 탐색에 사용될 수 있어 저장공간 활용도가 높다고 할 수 있다.

 

 

하지만 하나의 노드에 너무 많은 데이터를 저장해버리면 2차저장소에서 하나의 block에 담을 수 있는 데이터양을 초과해버릴 수 있다. 그럼 노드 접근이 일어날 때 총 2번의 block을 읽어와야 하기 때문에 하나의 block에 최대한 많이 담을 수 있는 데이터 개수를 확인하고 초과하지 않도록 설계하는 것이 효율적이다. 

 

 

여기까지 B-tree의 특징과 각각의 특징들이 탐색할 때 어떤 이점을 만드는지도 알아보았다. 그런데 탐색속도가 B-tree보다 더 빠른 자료구조가 있다. 바로 해시테이블이다. 해시테이블의 시간복잡도는 O(1)로, 이 뜻은 단 한번의 작업으로 데이터를 바로 읽어올 수 있다는 말이다. 저장공간 용량이 뒷받쳐준다면 데이터가 몇개가 있어도 단 한번의 작업만으로 탐색할 수 있다. (물론 저장되는 데이터들이 많을수록 해싱충돌이 일어날 수 있다)

 

 

하지만 해시테이블은 등호탐색만 할 수 있다는 단점이 있다. 즉 데이터베이스 인덱스로 사용된다면 범위검색을 하고 싶다면 단순한 해시테이블로는 탐색이 불가능하다. 해시테이블로 범위탐색을 하기 위해선 정렬된 저장공간을 따로 마련해서 해당공간에도 데이터를 넣고, 범위탐색할 때는 정렬된 공간에서 탐색을 할 수 있는 방법이 있을 수 있고, 해싱함수 자체를 범위탐색을 할 수 있도록 잘 구현하는 방법이 있을 수 있다. 하지만 그런 작업은 추가 저장공간이 필요하고, 해시테이블만이 가지는 빠른 탐색의 장점을 범위탐색을 위해서 성능에 영향을 줄바에 B-tree를 쓰는 것이 낫다. (다른 말로 데이터를 정렬하고 싶을 때는 해시테이블이 어울리지 않는다라고도 한다)

 

 

그럼 배열은 어떨까? 배열은 탐색을 효율적으로 할 수 있지만 삽입과 삭제 작업을 할 때는 좋은 성능을 보여주지 않는다. 삽입할 데이터는 정렬을 위해 중간에 넣어야 할때도 있는데, 중간에 넣게 되면 중간에 저장할 인덱스부터 데이터를 한칸씩 뒤로 옮겨줘야 한다.  만약 100만개의 데이터 중 인덱스 5에 새로운 값이 삽입된다면, 기존 인덱스 5에 있던 데이터부터 999995개의 데이터가 한칸씩 뒤로 옮기는 작업을 해야 한다. 삭제작업이 실행될때도 마찬가지다. 이 작업은 저장되는 데이터가 많아질수록 치명적이기 때문에 데이터가 계속 삽입되고 삭제될  수 있는 데이터베이스에서는 B-tree구조의 삽입, 삭제가 더 효율적이다.

 

 

결국 대량의 데이터가 저장된 데이터베이스에서 빠르게 탐색할 수 있고 삽입과 삭제 작업을 할 때도 효율적으로 처리하기 위해선  B-tree기반의 구조가 적합하다는 것을 알았다. DBMS에서는 온전한 B-tree구조보다 더 발전된 B+tree 또는 B+tree등 더욱 효율적으로 작업할 수 있도록 변경된 구조를 사용한다.