b-tree 정의 및 카테고리
-
self-balancing tree data structure
- self-balancing : 서브트리의 뎁스차이가 2이상 나지 않는 트리.
-
maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time
-
데이터를 소트해서 보관한다. 이로 인해, 서치가 가능하다.
-
BST랑 다른점?
- BST는 binary 트리이다. 차일드의 개수가 2개로 한정되어 있으나, B-tree는 차일드의 개수가 고정되어 있지 않다. (m차 b-tree 라고 부를때, m은 차일드의 최대 개수이다.) -
로그시간
O(logN)내에 접근, 삽입, 삭제가 가능하다. 또한 공간 복잡도도O(n)이다.
-
시간복잡도
| method | timecomplexity(big O) |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
공간복잡도는 O(n).
b-tree 정의
B-tree of order m is
1.Every node has at most m children.
2.Every internal node has at least ⌈m/2⌉ children.
3.Every non-leaf node has at least two children.
4.All leaves appear on the same level and carry no information.
5.A non-leaf node with k children contains k−1 keys.
즉 m차 b-tree는 최대 m개의 차일드를 가지는 트리이다.
이 특성을 지키는 식으로 메서드들을 (insert, delete)구현해주면, 위에서 보았던 시간복잡도의 효율로 트리를 이용 할 수 있다.
b+tree
b+tree는 b-tree의 변형으로,
b-tree는 데이터가 각 트리의 노드마다 있지만, 이 b+tree는 마지막 leaf에만 데이터가 저장되어있다.
좋은 점으로는 leaf node에 linked list로 데이터를 보관해서, 선형적인 접근도 쉽게 가능하다.
가장 간단한 예로,
key가 1,2 인 데이터를 b-tree에서는 두번다(데이터가 leaf에 있다 치자) logN이 걸리지만, b+tree에서는 1을 logN으로 찾고, 다음 2는 linked list를 통해서 바로 접근이 가능하다.
b-tree가 쓰이는 곳
1. File System
최근의 리눅스 파일시스템을 보면 ext4 포멧을 볼 수 있다.
이 파일시스템은 내부적으로 b-tree를 기반으로 한 데이터 구조를 사용하고 있다.
wiki에서 보면
디렉터리를 관리할 때 hashed B-tree 를 사용하는 것을 알 수 있다.
2. DB
DB가 데이터를 저장 할 때 b+/b-tree를 사용한다.
직관적인 생각으로, DB는 특정 자료를 조건에 맞게 search하는 일이 굉장히 많으므로, search tree 를 쓰는것이 효과적일 것이고, 또한 depth가 너무 크면 성능에 문제가 있는데, bst 사용시에는 depth가 log2N 로 큰거보다 depth가 짧은 것을 선호 할 것이다. (서치big O가 짧아짐)
그러므로, b-tree 같은 child수가 좀더 많은 즉, depth가 더 작은 것을 사용하는 것이 좋고, 이로 인해 b+/b-tree 를사용하는 듯 하다.
물론 DB의 철학에 따라 이 구조를 그대로 쓰지않고 변형해 쓸 듯 하다.
