https://velog.io/@emplam27/자료구조-그림으로-알아보는-B-Tree

데이터 베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종

검색, 삽입, 삭제 모두 O(logN) 의 성능

대량의 데이터를 처리해야 할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 상당히 큰 장점이다.

대량의 데이터는 메모리 보다는 하드디스크 혹은 SSD에 저장되어야 하는데 이들 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문

ex) 한 블럭이 1024 바이트면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용 발생. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다.

→ B-Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 사용

• 한 노드에 최대 M개의 자료가 있으면 M차 B-Tree 라고 불림
• Root 노드 제외한 나머지 노드들은 최소 M/2 개의 자료를 가지고 있어야 한다
• Root 노드도 최소 2개 이상의 자식을 가져야 한다
• 각 노드의 자료는 정렬 되있어야함
• 모든 leaf의 깊이가 같다

B - Tree vs B+ Tree

• 각 노드에 데이터가 저장됨

• 그래서 key와 data 모두 저장

• data는 disk block로 포인터가 될수 있음

• 최상 케이스는 루트에서 끝남

• leaf 노드에만 데이터가 저장됨

• 각 노드에는 key만 들어감

• add, delete 모두 leaf 노드에서만 이루어짐

• 무조건 leaf 노드까지 내려가야됨

• leaf 노드끼리 linked list 되있어 범위 탐색에 유리