하드 디스크
왜 DB가 B-Tree를 선택 했는지를 알기 위해서는 우선 하드 디스크에 대해 알아야 한다.
하드 디스크는 순차 IO를 할 때는 큰 차이가 없지만 랜덤 IO가 발생할 때는 디스크 헤더를 돌려가면서 데이터를 읽을 지점을 찾는 작업을 하게 되는데 이게 처리량에 안좋은 영향을 준다.
그럼 이 내용을 기억하고 BST, AVL Tree, RB Tree, B Tree에 관해서 알아보자.
레코드와 색인
예를 들어서 ID, 이름, 전화번호, 성별을 스키마로 가지는 테이블이 있다고 가정할 때 이름, 전화 번호, 성별 등은 레코드의 데이터가 되게 된다. 그리고 ID는 이 테이블을 대표하는 색인이 되고 이를 PK라고 한다.
Binary Search Tree
이진트리는 맨 마지막 노드를 제외한 모든 노드가 자식을 2개씩 가지는 트리이다.
이진트리의 높이는 O(log n)이 되는데 데이터의 개수가 커질수록 트리의 높이가 증가한다. 또 일반적인 DB는 한 번의 탐색에서 여러 개의 데이터를 한꺼번에 불러오는 페이지 접근 비용을 줄여야 하는데, 이진탐색트리는 디스크 접근이 많아져 비효율적이다.
예시로 1 ~ 14까지의 데이터가 들어간 트리가 있다고 가정하자. 그러면 1~14까지의 색인을 기준으로 탐색을 N(log N)만큼 랜덤 IO를 발생시키며 탐색하게 된다.
또한 트리 정렬의 단점에서도 알 수 있듯이 트리가 편향된 구조로 될 경우 최대 O(n)의 탐색 시간이 걸릴 수 있다.
BST가 DB의 Index로 B-Tree보다 적합하지 않은 이유
- 노드 수가 많아질 경우 높이가 높아진다.
- 탐색 비용이 너무 많이 든다. (최대 O(N), 삽입시 O(N^2))
- 랜덤 IO 발생 빈도가 크다.
삽입시 O(N^2)이 되는 이유는 편향 문제 때문인데 이러한 편향 문제에 대비하기 위해서 나온게 균형트리(AVL Tree와 Red Black Tree)이다.
AVL Tree
AVL 트리는 Adelson-Velskii와 Landis 두 사람이 고안한 트리로 이진 트리가 항상 균형을 유지하도록 운영하는 대표적인 예다. AVL 트리 내의 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않게 유지되는 이진 검색 트리이다.
- 삽입
- 균형이 맞지 않는 경우 회전함
즉, 삽입/삭제시에 이진탐색트리처럼 삽입/삭제를 하고 높이를 검증해서 균형이 안맞는 경우 좌회전/우회전 시켜준다.
AVL Tree가 DB의 Index로 B-Tree보다 적합하지 않은 이유
- AVL 트리는 균형을 유지하기 위해 삽입과 삭제 후 균형 검사를 수행하고 필요할 경우 회전을 수행하는데, 이 회전 연산이 빈번히 발생해서 성능 저하를 초래할 수 있다.
- 이진 트리에 기반하기 때문에 높이가 높아진다.
- 마찬가지로 Node를 두 개 들고 있기 때문에 랜덤 IO 횟수가 많아진다.
RB Tree
Red와 Black 두 색을 사용해서 균형을 맞춘다고 해서 RB(Red-Black) 트리라고 한다. RB 트리는 B-트리의 한 계열인 2-3-4트리와 사실상 같은 것이다.
RB 트리는 null 리프 노드를 가정하는데, 통상적인 이진 검색 트리에서 자식이 없으면 해당 링크를 null 값으로 두지만 RB 트리는 이 null 각각을 리프 노드로 간주한다. 즉, RB 트리에서는 통상적인 리프 노드 다음에 null 리프 노드가 한 층 더 있다고 가정하는 것이다.
RB Tree의 성질
RB 트리는 모든 노드에 레드 또는 블랙의 색상을 칠해야 하는데 다음과 같은 성질을 만족하도록 한다.
- 루트는 블랙이다.
- 모든 리프 노드는 블랙이다.
- 루트로부터 임의의 리프 노드에 이르는 경로에 레드 노드 2개가 연속으로 출현하지 못한다.
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
RB Tree가 DB의 Index로 B-Tree보다 적합하지 않은 이유
결국 다른 이진 트리 기반의 트리들과 유사한 이유인데, RB Tree 역시 트리 높이가 높고 회전 연산이 필요하다.
