오늘은 면접 질문을 준비하면서 예전 면접에서 답하지 못했던 내용, 내가 말로는 알고 있지만 진짜로 이해하지 못했던 부분을 정리해나갔다. 그런 과정에서 정리하고 싶은 내용을 오늘의 TIL로 남겨본다.
DB에서 인덱스를 구성하는 자료구조로 가장 기본적으로 사용하는 것이 바로 B tree이다. 이 B tree가 어떤 구조이고, 어떻게 삽입, 삭제를 하기에 효율적인지, 그리고 B tree와 B+ tree의 차이를 알아보도록 하자.
일단 B tree를 알기 전에 먼저 알아야 하는 자료 구조가 있다. 한번 그를 차근차근 살펴보자.
2-node, 3-node … n-node
기본적으로 우리가 알고 있는 tree의 node는 하나의 key를 가지고 0개 이상의 child node를 가지는 것이라고 알고 있다. 하지만 node의 key는 여러개가 될 수 있으며, 그러한 노드들을 이름 붙여 정의해놓았다.
2-Node는 key가 1개, 그리고 그 child node가 2개인 노드 구성을 일컽는다. 그리고, 3-Node는 key가 2개, 그리고 그 child node가 2개인 노드 구성을 말한다.
2-Node 3-Node
그리고 n-Node 는 key가 n-1개, child node가 n개인 노드를 말한다.
2-3 tree
위에서 설명한 2-Node와 3-Node의 형태인 node가 이루어진 트리가 있는데, 그것이 바로 2-3 tree이다. 그리고 2-3 tree는 균형트리라는 속성을 가진다. 이 조건 때문에 삽입 삭제가 특이하다.
2-3 트리의 삽입은 일단 기본적으로 맞는 위치를 탐색하고, 해당 노드가 삽입될 노드를 찾는다.
이렇게 삽입될 노드를 찾으면, 그 삽입될 노드가 어떤 상태인지에 따라 동작이 달라진다.
그림을 통해서 더 자세히 알아보면 다음과 같다.
위의 사진과 같은 트리가 존재한다고 할 때, 여기서 58이라는 수를 삽입한다면 추가하는 해당 노드는 57일 것이다. 이는 첫번째 경우이기 때문에 단순히 (57, 58)의 3-Node가 형성된다.
만약에 35를 삽입한다면 어떨까? 이는 3번째의 경우에 해당한다. 35가 들어가야할 노드는 (33, 43) 노드일 것이다. 일단 (33, 35, 43) 형태의 4-Node가 만들어질 것이고, 중간 값인 35가 부모의 Node로 들어가게 될 것이다. 그러면 Root Node 또한 4-Node가 된다. Root Node에서는 중간 값인 44 를 key로 하고, 35와 56을 child node로 하는 2-Node가 생성될 것이다.
삭제는 일단 2가지의 요소가 중요하다. 해당 노드를 삭제했을 때, 균형트리가 유지 되는지, 그리고 노드를 삭제할 때 key가 사라지는 Empty Node가 없는지이다. 삭제 후에 이러한 요소가 만족할 때까지 특정 작업을 한다.
삭제는 너무 복잡해서 직접 설명을 작성할 엄두가 안난다… 추가적으로 후에 보강해야겠다. 더 나은 설명이 필요한 분은 아래 포스팅을 참고하면 될 것 같다.
B Tree?
그래서 B Tree는 뭐냐고?
위에서 살펴본 2-3 Tree도 B Tree의 일종이다. 위처럼 N-Node의 형태를 가지는 Tree를 B Tree라고 하고, 2-3 Tree는 2차 B-Tree라고 말한다. 차수에 들어가는 것은 하나의 노드가 가질 수 있는 데이터의 수를 말한다.
다시 정리하자면, 2-3 Tree는 2차 B-Tree가 된다.
B+ Tree?
B Tree는 특성상 순회 작업이 매우 난감하다. 모든 tree의 노드를 방문해야하기 때문이다. 이런 순회 작업의 복잡성에 대한 문제를 해결하기 위해 제시된 것이 B+ Tree이다.
B+ Tree는 모든 데이터가 leaf 노드에 존재한다. 그리고 탐색을 위한 key값이 되는 Node들은 중복으로 Non-leaf 노드를 구성하게 된다. 즉, 값을 찾기 위한 인덱스 노드와 실제로 그 값을 가지고 있는 위한 리프 노드가 분리되어서 존재하는 것이다.
그리고, 각 leaf node들은 전부 linked list로 연결되어 있어 순차 처리가 가능하다.
B+ Tree의 장단점
앞서 말했던 것처럼, 데이터에 대한 순차 순회에 대해서는 매우 큰 강점을 지닌다. 하지만 Search를 하는 경우에 B Tree는 빠르면 Root에서 끝날 수 있지만, B+ Tree는 무조건 Leaf Node까지 다다라야한다는 단점이 있다. Key가 담고 있는 실제 데이터는 아래의 Leaf Node가 갖고 있기 때문이다.
참고 포스팅