자료구조 B-tree 기본 개념 파악 (1)

한양대학교 연구실에 지원하면서 B-tree에 대해서 공부하였다.

 

컴퓨터 공학을 전공하지 않고 국비로 급하게 공부한 입장에서 자료구조의 중요성은 익히 들었지만 제대로 공부하진 않았었는데 이번 기회에 하나의 개념에 대해서는 꽤나 깊게 공부하였다. 

 

1. 자료구조 B-tree 개념 파악

2. 시간복잡도(Time Complexity) 및 공간복잡도 개념 파악

3. 트리 종류 여러 개 파악하면 좋지만 그 중에서도 가장 관련성 높은 이진 트리(binary tree) 개념 파악

4. B-tree 개념 다시 숙지

5. 왜 B-tree인지 파악

 

B-tree는 Balanced Tree의 일종이다. 

 

항상 밸런스를 유지해서 편향되지 않고 노드레벨이 편향된 것에 비해서 효율이 좋다.

 

이진트리 같은 경우 한쪽으로 편향될 경우 시간복잡도가 최악의 경우 O(N)으로 꽤나 비효율적이 될 수 있지만

 

우리의 B-tree는 최악의 경우에도 O(logN)이라는 빠른 속도를 자랑한다.

시간복잡도 개념은 다음에 설명하겠다. 생각보다 복잡하지만 야매로 간단하게 이해할 수 있는 방법을 설명하고자 한다. 그냥 아 저게 빠르구나 아 저게 느린가보다 하고 넘어가자

<B-tree>

 

<Binary Tree>

 

 

B-tree와 이진트리의 차이점이 보이시나요?

 

B-tree는 Balance있게 양쪽으로 데이터들이 들어가지만 Binary Tree같은 경우는 왼쪽은 가득, 오른쪽은 하나만 들어가있습니다.

 

또한, B-tree에는 하나의 노드에 여러개의 데이터가 들어갈 수 있게 됩니다.

 

블로그마다 B-tree에 대한 설명이 미묘하게 다른 부분이 조금 있어서 위키피디아 영문판에서 정의들을 가져와서 공부했습니다.

 

루트노드는 트리에서 제일 위에 있는 노드를 지칭합니다!

 

Internal nodes

Internal nodes are all nodes except for leaf nodes and the root node. They are usually represented as an ordered set of elements and child pointers. Every internal node contains a maximum of U children and a minimum of L children. Thus, the number of elements is always 1 less than the number of child pointers (the number of elements is between L−1 and U−1). U must be either 2L or 2L−1; therefore each internal node is at least half full. The relationship between U and L implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there's room to push one element up into the parent). These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.

 

최대 U, 최소 L개의 자식을 간다. U = 2L or 2L-1. 그리고 최소한 절반 이상은 채워져있어야한다.

 

Leaf nodes

In Knuth's terminology, leaf nodes do not carry any information. The internal nodes that are one level above the leaves are what would be called "leaves" by other authors: these nodes only store keys (at most m-1, and at least m/2-1 if they are not the root) and pointers to nodes carrying no information.

 

리프노드는 트리에서 제일 아래에 위치한 노드들이다.

핵심은 이 노드들은 자식이 없다! 최대 m-1개, 적어도 [m/2]-1개의 keys를 가져야한다. (단, 리프노드가 루트노드가 아닌 경우)

 

 

노드 개념을 알았으니 B-tree의 정의를 살펴보면

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

1. Every node has at most m children.
2. Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.
3. The root has at least two children if it is not a leaf node.
4. A non-leaf node with k children contains k − 1 keys.
5. All leaves appear in the same level and carry no information

m차 B-tree의 경우

1. 모든 노드는 최대 m개의 자식노드를 가진다.

2. 모든 리프노드와 루트노드를 제외하면 적어도 [m/2]개의 자식노드를 가진다. ( [ ]는 올림연산이라고 하네요. 아주 확실한 정보는 아닙니다.)

3. 리프노드가 아니라면 루트노드는 적어도 두개의 자식노드를 가진다.

4. 리프노드가 아닌 노드들은 k개의 자식노드가 있다면 k-1개의 데이터를 가진다. (한 노드에 k-1개의 keys가 있다는 뜻)

5. 모든 리프노드들은 같은 레벨에 존재하고 정보를 전달하지 않는다.

 

 

결국 핵심은 루트노드와 리프노드에서 예외사항은 많다.

 

각각 정보를 정확히 알아둘 필요가 있었다.

 

다음은 시간복잡도 개념을 이야기해보아야겠다.

 

복잡하지 않고 간단하게