B+ Tree 이해하기
드디어 B+ Tree까지 왔다. 이제 이것만 하면 코딩 시작...!!!! 빨리 이해해야지 .. 후...
B+ Tree는 B Tree의 변형된 버전으로 데이터베이스 인덱스 구조에서 매우 많이 사용되는 자료 구조이다. B Tree와 유사하지만 몇가지 차이점이 있어서 대용량 데이터 검색에 최적화된 특성을 가지고 있다.
B+ Tree는 균형 다진 트리(Balanced Multiway Tree)로 B Tree와 마찬가지로 데이터를 효율적으로 관리하고 검색하기 위한 트리 구조이다. 하지만 B Tree와 달리 모든 실제 데이터는 리프 노드에만 저장되고 내부 노드는 오직 인덱스 역할만 한다.
B+ Tree의 구조 및 특징
· 리프 노드
실제 데이터를 저장하고 각 리프 노드에는 다음 리프 노드로의 포인터가 존재한다. 이를 통해 연결 리스트처럼 모든 리프 노드가 연결되어 있어 범위 탐색에 유리하다.
리프 노드의 키 값들을 삭제해도 내부 노드의 키 값은 유지된다. 당연히 내부 노드는 리프 노드의 키 값을 찾아가기 위한 기능을 하니 내부 노드의 값들은 유지되어야 한다.
· 내부 노드
인덱스 역할을 한다. 각 내부 노드에는 키 값만 저장되고 리프 노드에 있는 데이터를 가리키는 포인터가 있다.
내부 노드는 리프 노드에 있는 키 값을 찾아갈 수 있는 경로만 제공한다. 물론 B Tree의 키 값들과 마찬가지로 정렬된 상태를 유지한다.
· 트리의 차수(Order)
B Tree와 마찬가지로 하나의 노드가 가질 수 있는 최대 자식 수를 나타낸다. 예를 들어, 차수가 m인 B+ Tree에서는 각 내부 노드가 m-1개의 키를 저장하고 최대 m개의 자식을 가질 수 있다.
· 키 값의 중복을 허용하지 않는다.
B+ Tree는 키 값의 중복을 허용하지 않는다. 각 키 값은 유일해야한다.
- 노드 개수를 왜 n/2에서 n개까지 유지해야할까?
B+ Tree의 삽입과 삭제를 반복하다보면 어떤 노드에는 2-3개의 키만 남고 루트노드에서 리프노드까지의 멀어지게 된다. 노드 하나가 disk chunk 하나에 대응되기 때문에 chunk를 건너뛰는 연산이 된다. 매우 많이 걸린다는 뜻이다.
- n/2개 말고 70%만 가지고 있게 해도 될까?
된다. 좀 더 많은 숫자의 키를 사용해도 되지만 n/2로 하면 알고리즘 개발이 더 편해서 이렇게 만들어진 것이다.
한번 쪼갤 때 n/2개로 쪼개진다. 따라서 이를 따라서 최소 개수로 정한 것이다.
- 1 2 4 에서 7을 삽입할 때 어떠한 것을 split key로 가져가야할까?
4 2
1 2 4 7 1 2 4 7 둘다 가능한 구조이다. 짝수 개를 쪼개야할 때는 중간에 있는 두 개의 숫자 중 어떠한 것을 선택해도 상관없다.
- 리프노드에 있는 키를 삭제할 때 삭제할때 위에 있는 내부 노드를 삭제해야할까?
안 지워도 괜찮다. non-leaf 노드의 수를 줄이기 위해서 지우는 것이다. 하지만 degree가 100 이상인 트리의 깊이에는 크게 영향을 미치지 않기 때문에 내부 노드를 지우지 않아도 상관없다.
시간복잡도 계산
리프 노드가 연결 리스트의 형태를 띄기 때문에 선형 검색이 가능하다. 따라서 굉장히 작은 시간복잡도에 탐색을 수행할 수 있다.
B Tree와 마찬가지로 B+ Tree도 탐색에 O(log(n))만큼의 시간 복잡도가 소요된다. 다만 범위 탐색 진행시에는 훨씬 효율적이다.
B Tree
N개의 데이터가 저장된 B Tree에서 m(i~j)개에 대한 범위 검색을 한다고 하자. B Tree의 경우 하나의 데이터를 탐색하는데 O(log(n))만큼 걸리고 m개에 대해 탐색이 진행되어야 하므로 총 O(m*log(n))만큼의 시간이 소요된다.
B+ Tree
B+ Tree의 경우 리프 노드가 연결 리스트로 되어있으므로 범위 검색에 대한 시작점 i를 한 번 탐색하면 i부터 j까지 선형 탐색을 진행하면 된다.
i가 위치한 리프 노트까지 내려가는데 높이만큼의 시간 O(log(n))의 시간이 소요된다. 이제 i부터 j까지 m개의 데이터에 대해 선형 탐색을 하므로 m만큼의 시간이 소요된다. 총 O(m+log(n))만큼의 시간 복잡도가 소요됨을 알 수 있다.
B+ Tree의 주요 연산
1. 탐색(Search)
B Tree와 유사하게 진행된다. 내부 노드에서 이진 탐색을 통해 리프 노드로 이동하며 리프 노드에서 실제 데이터를 찾는다. 하지만 B Tree와 달리 내부 노드에는 데이터가 없고 리프 노드에만 데이터가 존재하므로 리프 노드에 도달할 때까지 인덱스 노드를 계속 탐색한다.
2. 삽입(Insert)
B Tree와 유사하게 진행된다. 데이터를 삽입할 위치를 탐색한 후 리프 노드에 데이터를 삽입한다. 리프 노드가 꽉 차게 되면 분할을 하고 중간 키를 부모 노드로 올려보낸다. 이때 리프 노드의 중간 키는 복제되어 부모 노드, 리프 노드에 모두 존재한다.
3. 삭제(Delete)
B Tree와 유사하게 진행된다.
리프 노드에서 삭제를 한 후 키의 수가 최소 허용 값보다 적어졌다면 borrow나 merge의 과정을 통해 균형을 맞춰야한다.
1) 형제 노드에서 데이터 차용(Borrow)
형제 노드가 충분히 많은 키를 가지고 있을 때 왼쪽 형제 노드에서 차용할 가장 큰 키 혹은 오른쪽 형제 노드에서 차용할 가장 작은 키를 부모 노드로 올린다. 이떄 부모 노드에 있던 적절한 키를 현재 빈 노드로 내린다. 삭제할 k가 리프노드의 가장 처음 키라면 항상 k는 index 내에 존재한다. 따라서 리프 노드 k를 삭제한 후 index내의 k를 오른쪽 자식 노드의 가장 작은 값으로 변경해주어야 한다.
2) 형제 노드에서 차용할 수 없는 경우 (Merge)
형제 노드에 충분한 키가 없어서 차용할 수 없는 경우는 병합을 해야한다. 두 노드를 하나로 합치고 부모 노드의 키 중 하나를 내리는 방식으로 균형을 맞춘다.
공부 끝..! 이제 파이썬으로 B+ Tree를 구현해보자ㅏ.. 파이팅...! ㅎㅎ...
과제가 더 시급해서 그래프 그림은 다시 패드로 그려서 올려야겠다. 사람들은 어디서 예쁜 그림들을 구해오는지 의문이다...!