[CS] B-Tree & B+Tree

B-Tree

이진 트리와는 다르게 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있다.

하나의 노드에 여러 정보를 담게 되고, 여러 자식을 가질 수 있게 되면서 차수라는 개념이 등장함.

규칙에 맞게 정해진 범위만큼의 키가 하나의 노드에 포함될 수 있다.

B-Tree는 균형이진트리의 연속이라 자연히 균형을 유지한다. 아무리 최악의 경우라도 O(logN)의 검색 성능을 보여준다.

규칙

• 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
• 각 노드의 자료는 정렬된 상태여야함
• 루트 노드는 적어도 2개 이상의 자식을 가져야함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야함
• 외부 노드로 가는 경로의 길이는 모두 같음.
• 입력 자료는 중복 될 수 없음

 

하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담을 수 있음.

 

하드디스크나 SSD와 같은 외부 기억장치는 블럭단위로 파일을 입출력한다. 이때 발생하는 입출력의 비용은 파일의 크기와는 상관 없이 동일하다. 입출력에 있어서는 1KB짜리 블럭에 1byte짜리 알파벳 하나가 들어가 있어도 1KB가 꽉 차있는 블럭과 비용 차이가 없다는 것.
하나의 블럭에 여러 데이터들을 동시에 저장할 수 있다면 블럭을 보다 효율적으로 사용할 수 있기 때문에 많은 데이터베이스들은 B-Tree를 이용한다.

 

직접 B-Tree를 생성하는 것을 볼 수 있는 사이트
https://www.cs.usfca.edu/~galles/visualization/BTree.html

 

---

 

B+Tree

B-Tree는 탐색을 위해서 노드를 찾아서 이동해야 한다는 단점을 가지고 있다. 단점을 해소하기 위해 B+Tree는 같은 레벨의 모든 키값들이 정렬되어 있고, 같은 레벨의 Sibiling node(형제 노드)는 연결리스트 형태로 이어져 있다.

(같은 레벨의 Sibiling node는 모두 연결되어 있어서 키값이 중복되지 않는다.)

 

만약 특정 값을 찾아야 하는 상황이 된다면 leaf node에 모든 자료들이 존재하고, 그 자료들이 연결리스트로 연결되어 있으므로 탐색에 있어서 매우 유리하다. 단, 데이터 검색 시 반드시 leaf node까지 내려가야 한다.

 

leaf node 자료를 데이터 노드라고 부르고, leaf node가 아닌 자료를 인덱스 노드라고 부른다.

데이터 노드의 value값에 데이터가 존재하고, 인덱스 노드의 value값에 다음 노드를 가리킬 수 있는 포인터 주소가 존재한다. 

 

특징

1. 데이터 노드의 자료는 정렬되어 있다.
2. 데이터 노드에서는 데이터가 중복되지 않는다.

3. 모든 리프는 같은 레벨에 있다.

4. 리프가 아닌 노드에 있는 키값의 수는 그 노드의 서브트리 수보다 하나 적다.

5. 모든 리프 노드는 데이터 파일의 순차 세트를 나타내며 연결리스트로 연결되어 있다.

 

직접 B-Tree를 생성하는 것을 볼 수 있는 사이트

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

 

참고

https://code-lab1.tistory.com/217

https://ssocoit.tistory.com/217

https://weejw.tistory.com/182

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree