5. 이진 탐색 트리와 B-Tree 의 등장 배경

이번 글부터는 가장 유명한 저장 구조인 B-Tree 를 이해하는데 있어 필요한 기본적인 개념들을 정리한다.

지난 글에서도 언급했듯 B-Tree 는 mutability 를 갖는 저장 구조이다.

그리고 대부분의 mutability 구조는 in-plcae update 메커니즘을 사용한다.

이 말은 데이터를 삽입, 수정, 삭제하는 연산을 수행할 때, 그 데이터가 저장된 그 파일 안에서 연산이 일어난다는 것을 말한다.

 

어떤 스토리지 엔진은 같은 데이터 레코드의 여러 버전을 동시에 저장하기도 한다.

다중 버전 동시성 제어, Slotted Page 가 그 예시이다.

하지만 이해를 간단히 하기 위해, B-Tree 를 정리할 때는 하나의 데이터 레코드가 저장된 위치는 유일하다고 가정하자.

 

Binary Search Tree

B-Tree 에 대해 정리하기에 앞서, B-Tree 이전에 존재했던 다양한 트리 자료구조에 대해 정리해보자.

자료구조 수업에서 원하는 데이터를 로그 시간에 찾을 수 있는 이진 탐색 트리에 대해 배웠었다.

왜 이진 탐색 트리라는 유명한 데이터 탐색 자료구조를 두고 B-Tree 를 사용하는 것일까?

 

BST 는 in-memory 자료구조로, key-value 데이터 탐색에 사용된다.

트리의 각 노드는 value와 연관된 key 값을 가지고 있으며, 2개의 자식 노드의 주소가 저장된 2개의 포인터를 갖고 있다.

 

트리는 root node 라고 부르는 하나의 노드에서부터 시작되며, 각 트리의 root node 는 유일하다.

모든 노드는 탐색 공간을 좌/우 2개로 나누며, 각 노드의 키 값은 왼쪽 서브트리의 키 값들보다 크고, 오른쪽 서브트리의 키 값들보다 작다.

따라서 항상 왼쪽 자식 노드를 쭉 따라가서 내려가면 키의 최솟값을 찾을 수 있고, 반대로 항상 오른쪽 자식 노드를 쭉 따라가서 내려가면 키의 최댓값을 찾을 수 있다.

 

Tree Balancing

그런데 이진 탐색 트리에 삽입, 삭제 연산을 수행하다보면 모든 데이터가 왼쪽 또는 오른쪽에 치우치게 저장되는 경우가 발생할 수 있다.

이렇게 phthological 하게 저장하면 마치 트리가 아니라 연결 리스트에 데이터를 저장하는 것과 같기 때문에, 일반적인 BST 처럼 빠르게 데이터를 탐색할 수 없다.

따라서 성능을 높이려면 매 키 값을 확인할 때마다 탐색 공간이 반으로 줄어들어 로그 시간복잡도로 데이터를 찾을 수 있도록, 트리의 좌우가 균형잡힌 balanced tree 형태를 유지하도록 해야 한다.

 

균형잡힌 트리는 데이터의 개수가 N 일 때 높이가 log₂ N 이며, 왼쪽 서브트리의 데이터 개수와 오른쪽 서브트리의 데이터 개수 차이가 1을 넘지 않는다.

이렇게 트리의 균형을 유지하려면, 노드를 추가할 때마다 트리의 높이를 최소화하면서도 각 노드가 BST 의 정의에 맞춰 정렬되어 있도록 트리를 재구성해야 한다.

노드의 삽입/삭제 후 트리의 규형을 유지하도록 트리를 재구성하는 방법 중 하나는 트리를 회전시키는 것이다.

 

예를 들어 노드에 대한 연산 결과 3개의 노드가 연속해서 한쪽 방향으로 이어져 있다고 해보자.

이 경우 가운데 노드를 pivot 으로 잡고 회전시켜, 가운데 노드를 root 로 하고, 자신의 앞 뒤 노드를 각각 좌/우 자식 노드로 하는 트리로 재구성할 수 있다.

(즉, 가운데 노드의 부모 노드를 가운데 노드의 오른쪽 자식 노드로 만들고, 가운데 노드를 이전 부모 노드의 위치로 이동)

 

 

디스크에서의 BST

BST 의 성능을 결정하는 요인에는 balancing 여부 외에도 fanout 이 있다.

fanout 은 하나의 노드가 가질 수 있는 자식 노드의 최대 개수를 말하며, BST 의 fanout 은 2 이다.

BST 는 이 fanout 값이 작기 때문에, 삽입 삭제가 일어날 때마다 트리를 자주 재구성해야 한다.

 

특히 디스크에서는 트리를 재구성하는 비용이 더 크기 때문에 BST 를 실용적으로 쓰기 힘들다.

거기에 디스크에서 BST 를 쓸 때는 몇 가지 문제점이 더 있다.

 

1. locality

데이터가 추가되는 순서는 정해져있지 않기에, 비슷한 값을 비슷한 위치에 저장할 수 없다.

즉, 자식 노드에 대한 포인터가 디스크의 여러 페이지에 흩어져있기 때문에 비슷한 값을 찾을 때, 디스크 여기 저기를 탐색해야 한다.

 

예를 들어 데이터를 1 5 2 4 3 순으로 삽입한다고 해보자.

 

그러면 

 

         1

                \

                     5

                /

          2

               \

                 4

                /

             3

 

형태로 데이터가 저장된다.

그리고 1, 2, 3 이라는 3개의 데이터를 연속적으로 조회하고 싶을 때, 데이터를 찾기 위해 5, 4 라는 관련성이 없는 데이터를 자주 경유해야 하므로 필요없는 디스크 페이지를 여러번 읽어들여야 한다.

만약 비슷한 값을 가진 데이터가 최대한 부모-자식 간 인접하게 존재하도록 만들 수 있다면 디스크에서 읽어들여야 하는 페이지의 수를 줄일 수 있을 것이다.

이 문제는 트리 레이아웃을 수정하거나, paged binary tree 를 사용해서 어느 정도 해결할 수 있다.

 

 

2. 큰 트리 높이

BST 는 fanout 이 2밖에 되지 않기 때문에 트리 높이를 log₂ 단위로 밖에 낮추지 못한다.

그리고 디스크에 저장할 때 트리 높이는 중요하다.

트리의 높이가 높다면 데이터를 찾을 때 자식 포인터를 평균적으로 더 많이 따라가야 하는데,

자식 포인터를 따라 데이터를 탐색하는 것은 곧 디스크 탐색과 직결되고,

디스크 탐색은 메모리 탐색에 비해 느리기 때문에 성능에 큰 영향을 주기 때문이다.

 

게다가 만약 트리의 단일 노드 하나에 저장하는 데이터 크기가 작다면 그 비효율성이 더욱 증가한다.

디스크는 반드시 '블록' 이라는 고정된 크기 단위로 데이터를 읽고 쓰기 때문에, 작은 데이터 하나를 찾기 위해 필요없는 데이터를 대량으로 반복해서 읽어들이게 되기 때문이다.

따라서 2-3 tree 와 같이 낮은 fanout 을 가진 트리는 디스크보다 메모리에서 사용할 때 효율이 좋다.

 

 

정리하면 BST 를 나이브하게 구현해서 디스크에 대해 사용하면 성능이 좋지 않다.

BST 는 locality 를 고려하지 않은 자료구조이기 때문에 많은 디스크 탐색을 필요로 하기 때문이다.

따라서 디스크에 적합한 자료구조는 다음과 같은 특성을 가져야 한다.

 

1. 높은 fanout : 이웃 키에 대한 locality 를 개선할 수 있다.

2. 낮은 height : 키를 탐색하는 횟수(=디스크 탐색 횟수)를 줄일 수 있다.

 

그리고 이 두 속성은 사실 반비례 관계를 갖고 있다.

fanout 을 높이면 하나의 자식 아래에 더 많은 자식을 둘 수 있으니 자연스럽게 트리의 높이가 낮아지기 때문이다.

 

 

디스크 기반 저장 매체의 구조

DBMS 를 메모리 기반과 디스크 기반으로 분류할 수 있듯이,

자료 구조도 메모리에 저장하기 적합한 자료구조와 디스크에 저장하기 적합한 자료구조로 분류할 수 있다.

자료구조의 공간 / 시간 복잡도가 시스템 요구사항을 만족한다고 해도, 디스크에서 사용하기에 적합하지 않을 수 있다.

 

on-disk 자료구조는 데이터 양이 너무 많아서 모든 데이터를 메모리에 저장할 수 없을 때 사용한다.

특정 시점에는 데이터의 일부만 메모리에 캐싱되고, 나머지 데이터는 효율적으로 접근할 수 있는 방식으로 디스크에 저장된다.

 

하드 디스크

하드디스크는 원판이 겹겹히 쌓여있는 모양의 저장 매체이다.

각 원판에 데이터를 읽는 바늘을 두고, 원판을 회전시켜서 데이터를 읽어들인다.

과거 자료구조는 이 하드디스크의 구조에 맞춰 개발되었고, 플래시 드라이브와 같이 새로운 자료구조가 등장한 후에는 그에 맞게 새로운 자료구조가 등장하고, 기존 자료구조도 수정되었다.

 

하드 디스크는 물리적으로 원판을 회전시키고 바늘(헤드)을 이동시켜야 하므로, random access 비용이 크다.

하지만 한번 접근한 이후에, 연속적인 바이트를 읽는 sequential I/O 비용은 상대적으로 낮다.

 

하드 디스크의 물리적인 데이터 읽고 쓰기 단위는 '섹터' 이기 때문에, 한 번의 읽기/쓰기 연산을 수행하는 것은 곧 하나의 섹터 전체에 대한 읽기 / 쓰기 작업이 발생하는 것을 말한다.

보통 섹터 하나에 저장되는 데이터의 크기는 512byte ~ 4kb 정도 이다.

 

 

SSD

SSD (solid state drive) 는 움직이는 요소가 없는, 메모리 셀의 집합이다.

각 메모리 셀은 하나의 string 으로 연결되며, 각 스트링에는 32 ~ 64개의 셀이 연결되어있다.

각 string 들은 모여서 array 를 구성하고,

각 array 들이 모여서 page 를 구성하고, (운영체제의 페이지와 다른 개념)

각 page 들이 모여서 block 을 구성한다.

 

하나의 셀은 사용된 기술에 따라 1 또는 2 bit 데이터를 저장한다.

하나의 페이지는 보통 2 ~ 16kb 의 크기를 갖는다.

하나의 block 은 보통 64 ~ 512 개의 페이지를 갖는다.

 

각 블록들은 하나의 plane 안에 배치되고,

각 plane 들은 하나의 Die 안에 배치되어 있다.

 

SSD 에서 데이터를 읽고 쓰는 제일 작은 단위는 page 이다.

그리고 SSD 에서 데이터를 쓸 때는 반드시 비어있는 셀에 데이터를 써야 한다.

따라서 데이터를 수정하려면 셀을 지우고나서 데이터를 새로 써야 한다.

하지만 셀을 지울 때는 block 단위로만 셀을 지울 수 있다. (erase block)

그리고 빈 블록에 있는 페이지를 채울 때는 순차적으로 페이지를 채워야 한다.

 

SSD 는 FTL (Flash Translation Layer) 라는 컨트롤러 역할을 수행하는 소프트웨어 계층이 존재한다.

FTL 은 페이지 id 와 실제 저장 위치를 매핑하고, 각 페이지의 상태 (empty, written, discard) 를 관리한다.

또한 FTL 은 가비지 콜렉션 작업을 수행하며, 이 과정에서 안전하게 지울 수 있는 블록을 찾는다.

만약 지우려는 블록에 현재 사용중인 page 가 있는 경우, 해당 페이지를 새로운 공간에 쓴 뒤 page id 매핑을 변경하고 기존 블록을 지워서 데이터를 쓸 수 있도록 만든다.

 

SSD 와 HDD 모두, 데이터를 다룰 때 개별 바이트가 아닌 메모리 청크 단위로 주소 체계를 관리하기 때문에, 대부분의 운영체제는 데이터를 block 단위로 추상화해서 다루며, 1 word 데이터를 읽더라도 전체 블록 단위로 데이터를 읽게 된다.

그리고 SSD 에서는 HDD 와 달리 랜덤 엑세스와 엑세스 위치로부터 연속된 데이터를 읽는 성능 차이가 크지 않다.

 

가비지 컬렉션은 특히 랜덤 또는 정렬되지 않은 쓰기 작업시 성능에 악영향을 준다.

(여기저기 흩어진 곳에 쓰면 매번 가비지 컬렉션을 수행한다고 이해)

반면 쓰기를 할 때 항상 블록 전체에 대해 쓰거나, 같은 블록에 대한 쓰기 연속적인 쓰기 작업을 모아서 한번에 처리하면 I/O 횟수를 줄여 성능을 높일 수 있다.

나중에 buffering 과 immutability 특성 면에서 이런 최적화 기법을 정리한다.

 

 

디스크 기반 저장 매체에서 사용하는 자료구조

디스크 기반 저장매체에서 사용하는 자료구조 (on-disk 자료구조) 를 설계할 때 발생하는 제약 사항은 디스크 자체의 느린 access 속도 외에도 반드시 '블록' 단위로 데이터를 읽고 써야만 한다는 점이 있다.

블록 내의 특정 위치를 가리키는 포인터를 따라가려고 해도, 그 특정 부분만 읽는게 아니라 블록 전체를 읽어들여야 하기 때문이다.

따라서 이 문제를 해결하기 위해 on-disk 구조는 기존 자료구조의 레이아웃을 변경하여 디스크에 최적화되도록 만든다.

 

디스크에서는 '포인터' 의 개념이 지금까지 말한 것과 조금 다르다.

디스크에서는 모든 데이터 레이아웃을 직접 명시적으로 다뤄야 한다. (아니면 memory mapped file 을 쓸 수도 있다.)

디스크에서의 포인터는 기본적인 포인터와 비슷하지만, 타겟 포인터 값을 직접 계산하고 따라가야 한다.

 

대부분 on-disk 오프셋은 사전에 계산되어 있거나, 디스크에 실제로 쓰여지기 전까지 메모리에 캐싱되어 있다.

포인터가 가리키는 위치에 의해 만들어진 긴 의존성 체인은 코드와 구조 복잡도를 증가시키기 때문에, 포인터의 개수와 각 포인터가 가리키는 그 다음 포인터들의 범위를 최소화하는 것이 중요하다.

 

요약하면 on-disk 자료구조는 이 자료구조로 데이터를 저장할 저장 매체의 특성을 고려해서, 최소한의 횟수로 데이터에 접근할 수 있도록 설계된다. 이를 위해 locality 를 개선하고, 내부의 데이터 표현 방식을 최적화하고, 페이지를 가리키는 외부 포인터의 수를 최소화하면 된다.

 

BST 에서 높은 fanout 과 낮은 height 가 좋다는 최종 결론을 내릴 수 있었고,

위 내용을 통해 포인터는 추가적인 공간 오버헤드를 가지고, 밸런싱 과정에서 포인터가 변하면서 맵핑을 다시해야하는 오버헤드가 발생한다는 것을 알 수 있었다.

 

B-Tree 는 이 아이디어들을 종합적으로 적용하여 나온 on-disk 자료구조 이다.

 

1. fanout 을 높이고

2. 트리 높이는 최소화하고

3. 노드 포인터의 개수도 최소화하고

4. 밸런싱 연산의 수행 횟수도 최소화한다.

 

다음 글에서는 B-Tree 에 대해 자세히 정리해본다.