[DataBase][자료구조]B tree, B+tree

B tree 란?

B-tree는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조로 좌우 균형을 맞추어 트리의 검색,삽입,삭제 시 시간 복잡도를 개선한 자료구조이다.

 

 

B-tree는 아래와 같은 구조를 지니고 있다.

노드의 최대 숫자가 2보다 크다고 했으므로 최대 자식수가 3개면 3차 B-tree 4개면 4차 B-tree.... m차 B-tree라고 부른다.

 

• 루트(root) 노드
  • 최상단에 위치한 노드
• 리프(leaf)노드
  • 자식이 없는 최하단에 위치한 노드
• 내부(internal)노드
  • 루트노드와 리프노드를 제외한 모든 노드

 

B-tree의 규칙

• 노드의 데이터 수가 N개이면, 자식 노드 수는 N+1개여야 한다.
• root노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 지니고 있어야 한다.
• 노드 내 키(key)는 정렬된 상태여야 한다.
• leaf노드로 가는 모든 경로는 그 길이가 같아야 한다.(균형 트리)

'균형 트리' 란 루트로부터 리프까지의 거리가 일정한 트리 구조, 트리 중에서 성능이 안정화 되어있다.

B-tree는 처음 생성 당시는 균형트리이지만 테이블이 갱신(insert/update/delete)을 반복하며 균형이 깨지고 성능이 악화된다.

 

 

 

B-tree의 한계

InnoDB(MySQL 데이터베이스 엔진)은 B+tree로 인덱싱을 처리한다.

B-tree의 가장 큰 단점은 시퀀셜 엑세스 즉 순차적 접근에 취약하다는 것이다. 보통 우리는 데이터를 가져올 때 range를 정하고 해당 ragne에 속하는 데이터를 가져오는 작업을 한다.

B-tree는 루트부터 하향식으로 데이터를 찾아가기 때문에 복잡해질 수 있다. 또한 노드의 삭제/삽입 작업이 이루어지면 트리의 균형을 유지해주는 작업이 추가적으로 이루어져야 하기 때문에 트리의 깊이에 따라 Overhead가 커진다.

 

※Overhead: 어떤 처리를 하기위해 들어가는 간접적인 처리 시간과 메모리

ex) A라는 처리를 단순하게 실행하면 10초가 걸리지만, 안정성을 고려해 부가적인 B처리를 처리해 시간이 15초가 걸렸다면 5초의 오버헤드가 발생

 

 

B+tree 란?

B-tree의 단점을 보완하며 확장한 것으로 leaf node에만 데이터를 가지고 있고 나머지 노드들은 데이터를 위한 key만 갖는다.

Multilevel-indexing과 Linked-list가 핵심이다

가장 하단의 leaf node들끼리는 서로 liked list 형식으로 연결되어 있다.

 

B+tree의 장점

• 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있어서 트리의 높이가 더 낮아진다(cache hit를 높일 수 있음) -> 데이터 검색이 빨라짐
  • 노드에 더 많은 key를 담을수록 더 많은 데이터가 하나의 노드에 모여있게 되고, 메모리 캐시에서 한 번에 더 많은 데이터를 읽을 수 있게 된다.
• full scan시 B+tree는 리프 노드에 데이터가 모두 있어서  한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다

 

 

B-tree Vs B+tree 

아래서 말하는 데이터는 자료구조 상 value를 가리킴. (실제 DB 데이터 X)

구분	B-tree	B+tree
데이터 저장	리프 노드, 브랜치 노드 모두 데이터 저장 가능	오직 리프 노드에만 데이터 저장 가능
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔 시, 검색 속도	모든 노드 탐색	리프 노드에서 선형 탐색
키 중복	없음	있음(리프 노드에 모든 데이터가 있기 때문)
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

References

https://zorba91.tistory.com/293

https://fierycoding.tistory.com/78

https://escapefromcoding.tistory.com/731