b-tree

Concept

정의 : M-way Search Tree + AVL tree

- M-way search tree : 자식 노드가 최대 m개이고 최대 m-1개의 키를 갖는 탐색 트리

- 최소  𝑚/2(위로올림) 개의 자식을 가짐

 

쓰이는 곳

- database 와 file system에서 쓰임. 

 

복잡도

O(log n)