자료구조 및 알고리즘 11 - B+ Tree, BR Tree and Skip List

0. 들어가기 전

2024.05.14 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 10 - 2-3 Tree and 2-3-4 Tree

자료구조 및 알고리즘 10 - 2-3 Tree and 2-3-4 Tree

위 글을 통해 2-3 Tree 와 2-3-4 Tree 에 대한 기본적인 이해가 완료되었다고 가정하고 진행하겠습니다.

 

1. B+ Tree

 

기본적으로 B+ Tree 를 왜 사용해야하는 지를 알아야합니다.

 

B+ Tree 는 INDEX 구현을 할 때 사용됩니다.

데이터의 순차적인 탐색을 수행해야 할때 일반적인 B-Tree(* 2-3 Tree 같은것들) 은 데이터 하나를 찾고 그 다음 데이터를 찾을 때 다시 처음 루트노드부터 탐색을 수행해야만 합니다.

 

이는 메모리 상에서는 크게 문제가 되지 않을 수 있지만, 해당 데이터가 저장되어있는 곳이 하드 디스크와 같이 물리적으로 데이터를 읽어야 하는 공간이라면 얘기가 달라집니다.

 

하드 디스크의 디스크 팁이 섹터를 옮기는 데에 걸리는 시간은 매우 깁니다. 따라서 하드 디스크 상에서 데이터를 읽어들일때 유리하려면 한 번에 쭉 읽어들일 수 있어야 합니다.

 

이를 위해 B+ Tree 는 nonleaf node, 즉 단말 노드가 아닌 노드는 그저 INDEX 이고, 진짜 데이터들은 연결 리스트의 형태로 단말 노드에 존재합니다.

이렇게 된다면 데이터들을 순차적으로 탐색할 때에 다시 처음부터 탐색할 필요 없이 연결리스트를 통해 빠르게 접근이 가능합니다.

 

하지만 단점또한 존재합니다.

• B-Tree 의 경우 최상 케이스에서는 루트 노드에서 탐색이 끝날 수 있지만, B+Tree 에서는 반드시 단말 노드까지 내려가야 합니다.
• 중간 노드들이 데이터가 아닌 순수 INDEX 용이므로, 데이터만 저장하는 B-Tree 에 비해 메모리의 요구량이 증가합니다.
• 공간 사용의 비효율성 또한 존재합니다. B+Tree 는 각 노드마다 포인터값을 추가적으로 가지고 있어야합니다.

삽입 삭제에 대한 알고리즘은 나중에..(* 너무 복잡...)

 

2. Red-Black Tree

 

Red-Black Tree 는 기본적으로 2-3-4 트리의 다른 버전이라고 생각하면 편합니다.

 

2-3-4 Tree 에서 같은 노드끼리는 Red 간선으로 표현하고

2-3-4 Tree 에서 자식 노드로 표현한 것들은 Black 간선으로 표현합니다.

 

2-3-4 tree and RB tree

 

그렇다면 2-3-4 tree 에서 Split 을 해야하는 순간을 RB tree 에서는 어떻게 표현될까? 그리고 Split 을 수행한다면 RB tree 에서는 어떻게 될까?

 

우선 Split 해야하는 순간은 2-3-4 tree 에서 하나의 노드에 3개의 key 값이 들어있는 경우 RB tree 로 따지면 아래의 경우입니다.

또는 이런 경우도 가능합니다. 하지만 이 경우 추후 설명할 동작을 수행하여 균형 트리가 되어야합니다.

어쨋든, Split 을 수행한다면 RB tree 로는 어떻게 표현할 수 있을까?

 

이는 아래의 빨간색 간선 두 개를 위로 접은 것과 같습니다.

 

하지만 이때 문제가 발생할 수 있습니다. 위에서 설명한 케이스가 발생할 수 있다는 건데요.

아까 설명하지 않았지만 RB tree 는 자가균형 트리가 되기 위해 추가된 규칙이 있습니다. 바로 빨간색 간선이 연속해서 나올 수 없다는 것 입니다.

 

해당 규칙에 의해서

위 그림에 해당하는 tree 는 존재해서는 안됩니다. 따라서 AVL 트리에서 사용했었던, 회전을 사용합니다.(* RR case)

 

다른 예를 보면

해당 케이스의 경우 split 이 필요합니다. 그래서 split 을 수행한다면 

와 같은 tree 가 생성됩니다. 이때 연속된 두 개의 빨간 간선이 생기므로 LR case 에 대한 회전을 수행해준다면,

다음과 같은 tree 가 생성됩니다.

 

3. Skip List

 

skip list 는 기본적으로 연결 리스트입니다. 연결 리스트에서 빠른 검색 및 삭제를 가능하게 해주는 자료구조입니다.

 

skip list 의 특징으로는 랜덤성에 기초한다는 점입니다. 각 요소들에 대해 1/2 확률로 윗층으로 올라갈 수 있습니다.

이게 무슨말이냐면, 위에 그림에서 S0 에 있는 요소들, 12, 23, 26, 31, 34, 44, 56, 64, 78 들에 대해 각각 1/2 확률로 S1 에 올라올 수 있습니다. 위에 그림에서는 23, 31, 34, 64 가 올라왔습니다.

그리고 S1 의 요소들에 대해서도 각각 1/2 확률로 S2에 올라올 수 있고, 이를 레이어에 요소가 하나도 없을 때까지 반복합니다.

 

이를 통해 기존 연결 리스트가 검색에 걸리는 시간인 O(N) 에서 이진 탐색과 비슷한 수준인 O(logN) 으로 성능이 좋아집니다.

search(78)

 

삽입은 어떨까?

 

삽입의 경우, 검색과 비슷합니다. 일단 마지막 레이어까지 내려가고 삽입해야하는 값이 들어가야하는 자리에 값을 넣어줍니다. 이때도 1/2 확률로 위 레이어에 올라갈 수 있습니다.

Insert(15)

 

삭제는 어떨까?

 

삭제의 경우도 쉽습니다. 먼저 찾고 그 값을 삭제해주기만 하면 됩니다. 이때 고려해야할 점은 해당 요소가 해당 레이어의 유일한 요소인 경우와 삭제되는 요소의 아래에도 값이 존재하는 경우입니다. 하지만 이 경우들도 간단하게 처리할 수 있습니다.

 

삭제되는 요소가 해당 레이어에서 유일한 요소였을 경우:

해당 요소를 삭제한 후 해당 레이어도 같이 삭제해줍니다.

 

삭제되는 요소 아래에도 값이 존재하는 경우:

아래에 있는 요소들 전부다 삭제해줍니다.

Delete(34)