데이터베이스에서 B 트리(B+ 트리)가 유용하게 쓰일 수 있는 이유

B 트리와 B+ 트리는 데이터베이스에서 유용하게 쓰이는 자료구조라고 한다. 왜 데이터베이스에서 유용하게 쓰일 수 있는지에 대해 살펴보자.

 

Topics

1. 디스크 구조

2. 디스크에 데이터가 저장되는 방식

3. 인덱스

4. 멀티 레벨 인덱스

5. M-way 탐색 트리

6. B 트리

7. 레퍼런스

 

1. 디스크 구조

https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/10_MassStorage.html

https://sites.google.com/site/cis110oadrew/hard-drive-technology

디스크는 트랙과 섹터를 통해 데이터를 구분한다. 트랙은 육상 트랙과 같은 의미로, 위의 그림에서 빨갛게 칠해져 있는 구역이 하나의 트랙이다. 섹터는 피자를 잘랐을 때 한 조각에 해당하는 영역이다. 트랙과 섹터의 교집합을 블록이라고 하며, 블록은 트랙 번호와 섹터 번호를 통해 식별 가능하다.

 

블록 주소 = 트랙 번호 & 섹터 번호

 

블록은 바이트 수만큼의 칸으로 나누어져 있으며 각각의 칸은 오프셋이라는 주소를 갖는다.

 

디스크의 임의의 1 바이트 주소 = 트랙 번호 & 섹터 번호 & 오프셋

 

디스크에 대한 읽기/쓰기는 블록 단위로 이루어진다.

 

디스크의 특정 영역에 갈 때(데이터에 접근할 때)디스크의 회전을 통해 섹터를 찾고, 헤드가 앞뒤로 움직이며 트랙을 찾는 과정이 필요하다.

 

2. 디스크에 데이터가 저장되는 방식

아래와 같은 Employee 엔터티가 있다.

 

eid      10 bytes

name   50 bytes

dept    10 bytes

section 8  bytes

add     50 bytes

------------------

size = 128 bytes

 

eid	name	...
1	John	...
2	Phil	...

 

하나의 row는 128 bytes이며 100개의 row가 있다고 해보자. 디스크의 블록 사이즈가 512 bytes라면 하나의 블록 안에 4개의 row가 저장될 수 있으므로 100개의 정보를 모두 저장하기 위해서는 디스크의 25개 블록이 필요하다. 이때 특정 row를 찾고 싶다면 어떻게 해야 할까?

 

SELECT * FROM employee WHERE eid = 1;

 

최악의 경우 25개의 블록을 모두 살펴야 한다.

 

3. 인덱스

인덱스는 책 앞에 있는 목차 또는 책 뒤에 있는 인덱스를 생각하면 된다. 핵심은 보다 빠르게 탐색을 할 수 있게 도와준다는 것이다. eid와 row의 위치를 가리키는 포인터로 구성된 인덱스를 생각해보자.

 

eid	pointer
1	1번 사원 row의 주소
2	2번 사원 row의 주소
...	...

 

인덱스 역시 디스크에 저장된다. eid는 역시 10 bytes, 포인터는 6 bytes라고 가정한다면 512 bytes 1개의 블록에 32개의 인덱스 row가 담길 수 있다. 100개의 사원에 대한 인덱스이므로 4개의 블록이 필요하다. 따라서 이렇게 인덱스를 이용할 경우 25개의 블록이 아닌 인덱스를 찾기 위해 최대 4개의 블록을 살핀 뒤 마지막으로 row의 주소를 따라 1개의 블록만 더 살피면 된다.

 

계산은 그다지 중요하지 않다. 핵심은 인덱스를 이용하면 특정 row를 찾기 위해 뒤적여야 하는 블록의 수가 매우 줄어든다는 것이다.

 

4. 멀티 레벨 인덱스

데이터가 많아서 인덱스 크기 역시 커진다면? 그래서 인덱스를 찾기 위한 과정 역시 부담스러워진다면? 인덱스 row가 10000개라고 생각해보자. 인덱스의 크기는 여전히 16 bytes이므로 1개의 블록에 32개의 인덱스를 담을 수 있다. 따라서 인덱스를 저장하는 데 313개의 블록이 필요하다.

 

해결 방법은 같다. row를 찾기 위한 인덱스를 만들었듯, 인덱스를 위한 인덱스를 두면 된다. 이번에는 인덱스 row 하나에 대응되는 인덱스를 만드는 것이 아니라, 인덱스를 저장하는 하나의 블록에 대응되는 인덱스를 만들어보자.

 

https://youtu.be/aZjYr87r1b8 강의 중에서

 

두 번째 인덱스의 경우 첫 번째 인덱스를 저장하는 블록의 위치를 가리키므로 하나의 row당 첫 번째 인덱스를 32개까지 커버할 수 있다. 그래서 두 번째 인덱스의 두 번째 row가 1이 아니라 33인 것이다. 첫 번째 인덱스가 313개라고 하더라도 두 번째 인덱스는 10개의 row로 첫 번째 인덱스를 모두 커버할 수 있다. 이제 최악의 경우라고 하더라도 10 + 1 + 1개의 블록만 검사하면 원하는 row를 찾을 수 있다.

 

핵심은 계산 과정이 아니라 인덱스를 추가하면 검사해야 하는 블록의 수가 감소한다는 것이다.

 

5. M-way 탐색 트리

데이터 수가 매우 많아서 여러 겹의 인덱스가 필요하다고 생각해보자.

 

 

고개를 돌려보자.

 

 

트리가 보인다. 색칠된 영역을 하나의 노드라고 보면, 노드를 구성하는 키가 하나가 아니고, 노드의 자식 노드가 두 개가 아니다. 이와 같은 트리를 M-way 탐색 트리라고 부르는데, M은 노드가 가질 수 있는 자식 노드의 수와 관련이 있다.

 

* 키가 하나가 아니고 자식 노드가 두개가 아닌 것만 M-way 탐색 트리라고 부른다는 뜻은 아니다. M-way 탐색 트리는 일반화된 탐색 트리로, BST 역시 M-way 탐색 트리의 일종이다. 

 

하나의 노드에 하나의 키만 저장할 수 있고, 하나의 노드당 최대 두 개의 자식 노드만 가질 수 있는 BST와 달리 M-way 탐색 트리는 하나의 노드에 m-1개의 키를 저장할 수 있고, 한 노드당 최대 m개의 자식 노드를 가질 수 있다. 또한 각 노드를 이루는 key는 정렬되어 있다.

 

4-way 탐색 트리의 한 노드를 예시로 살펴보자.

 

 

한 노드를 구성하는 키는 정렬되어 있으므로 key1 < key2 < key3이다. Child1의 모든 key는 key1보다 작고, child2의 모든 key는 key1 보다 크다.

 

트리가 데이터베이스에서 사용되므로 한 종류의 포인터가 더 필요하다. 바로 데이터베이스의 특정 row(또는 row들이 저장되어 있는 블록)의 주소를 가리키는 포인터이다.

 

 

6. B 트리

멀티 레벨 인덱스를 표현하기에 M-way 탐색 트리가 제격인 것은 알겠다. 그런데 왜 B 트리를 쓸까?

 

멀티레벨 인덱스에서 필요한 것은 무엇인지 생각해보자. 인덱스가 트리 꼴이기 때문에 여느 트리와 마찬가지로 높이가 핵심이다. 높이를 최대한 낮게 유지해야 한다. 하지만 M-way 탐색 트리는 BST와 마찬가지로 skewed 트리가 될 수 있다.

 

https://stackoverflow.com/questions/25627454/creating-a-right-skewed-binary-tree-in-c

 

B 트리, B+ 트리가 바로 M-way 탐색 트리에 몇 가지 규칙을 더함으로써 트리에 노드가 추가되거나 제거될 때마다 트리가 skewed 트리가 되지 않도록 높이를 유지하는 트리이다. 그래서 데이터베이스에서는 B 트리가 유용하게 쓰일 수 있다.

 

---

 

B 트리에 어떤 규칙이 추가되었기 때문에 노드의 추가 또는 제거가 일어나도 트리가 기울지 않고 어떤 경우에도 높이가 logN으로 보장되는 것일까? B 트리에서 노드 추가와 노드 삭제의 과정은 어떻게 되는가? B+ 트리란 무엇인가? 이 부분에 대해서는 다른 글에서 다룰 예정이다.

 

인덱스도 이렇게 간단하게 지나칠만한 주제는 아니다. 인덱스에 대해서도 다음 기회에 더 구체적으로 다룰 예정이다.

 

인덱스를 구현하는 방식이 B 트리만 있는 것은 아니다. 어떤 종류가 있고, 어떤 차이가 있는지에 대해서도 나중에 정리할 예정이다.

 

7. 레퍼런스

https://youtu.be/aZjYr87r1b8