헷갈리고 어려울땐 목차정리를 해보자! 2 - 트리, B-Tree

1. B-트리란?

 기존의 트리는 1개의 노드에 1개의 데이터를 저장할 수 있었다면, B-트리는 1개의 노드에 여러가지의 데이터를 지니고 있다.

 이는 많은 정보를 더더욱 효율적으로 저장할 수 있으며 노드의 가지의 수와 높이가 기존의 트리구조보다 현저하게 적어질 수 있도록 해준다.

B-Tree 구조

 

2. 노드의 가지수가 적어지면 안좋은거 아닌가?

 B-트리는 앞서 말했다시피 하나의 노드에 많은 정보를 담고 있다. 이는 간선의 높이를 동일하게 만들어준다.

 기존 트리구조는 데이터를 하나만 담고 있었기에, 원하는 데이터를 찾기 위해서는 데이터를 찾고 다음 데이터로 이동하는 과정을       계속 거쳐야 했지만 B-Tree는 하나의 노드안에 여러개의 데이터를 담고 있기 때문에 다음 노드로 이동하는 과정을 많이 줄일 수 있다.

 따라서 다음노드를 찾는데에는 시간이 걸리겠지만, 노드 내부에서 데이터를 찾는데는 시간이 얼마 걸리지 않기 때문에, 데이터의 조회 시간을 줄일 수 있다.

또한, B-Tree는 규칙이 있는데 부모노드에서 뻗어나가는 간선의 갯수가 부모노드 내의 데이터의 갯수 + 1 이 되야한다.

4개의 데이터를 가진 부모노드는 총 5개의 자식을 가진다는 뜻이다.

이러한 규칙은 트리구조가 대칭적으로 되도록 도와주고, 이러한 대칭성 또한 데이터에 접근하고 다루는 것을 빠르게 만들어준다.

B-Tree 규칙

 

3. 의사 코드를 이용해 B-Tree의 기능을 구현해보기  

1) Searching (추가 조사 필요)

 // 노드간 이동시에는 기존의 트리에서 했던 방법을 이용한다.

 // 노드 이동 후 내부에서 데이터를 찾을 때는 0번째 인덱스 부터 순서대로 Searching을 진행한다.

 

2) Add

 // leaf node의 데이터공간이 있다면 그곳에 할당한다.

데이터 공간이 있을 때

 // leaf node의 데이터공간이 없다면, 현재 leaf node를 부모노드로 하는 새로운 자식노드를 생성하고 그 안에 데이터를 담는다.

데이터 공간이 없을 때

 

3)Delete

 // 삭제후 노드내의 데이터공간이 50% 이상 보장된다면, 그냥 두고

 // 삭제후 노드내의 데이터 공간이 50% 이하이라면 

 // 1. 데이터 공간이 50%이상 차 있는 형제 노드의 데이터를 50%만 남기고 가져온다.

 // 2. 형제노드들의 데이터가 모두 데이터공간의 50%만 차있다면, 데이터들을 모두 형제노드의 데이터 공간에 합친다.

delete 하는 경우