B-tree
-
[알고리즘] B 트리프로그래밍/알고리즘 2019. 4. 29. 16:44
기본개념 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해서 키를 다수 보유하고 있는 트리라고 할 수 있다. B-트리의 조건 모든 단말노드는 동일한 높이를 가진다. 각 내부노드의 자식노드는 M/2 이상 M 이하이다. (M은 2보다 큰 정수로서 트리노드의 최대 자식 수) 루트의 자식 수는 두개 이상이다. ...더보기 우리는 트리의 높이를 최소화 하기 위해 자가균형트리를 배웠다. (레드블랙트리, AVL 트리) B트리는 키의 갯수를 증가시켜 트리의 좌우를 넓히는 방법으로 높이를 낮췄다고 생각하면 도움이 될것이다. 탐색 B트리는 이진트리와 마찬가지로 중위순..