넘치게 채우기

B+트리 B+트리는 기존의 B트리에서 확장된 버전이라고 볼 수 있다. 다음과 같은 특성을 가지고 있다: 1. 모든 key와 value를 leaf 노드에 가지고 있다. 2. 모든 leaf 노드가 연결리스트로 이어져 있다. 3. 내부노드는 데이터 참조를 위한 인덱스 역할만 한다. 이러한 특성으로 검색, 삽입, 삭제 모두 빠르게 수행할 수 있다. 대용량 데이터베이스에서의 인덱싱에 사용된다. B+트리의 삽입 삽입과 삭제 과정에서, t = floor(M/2)로 한다. Case 1. 분리되지 않는 경우: 기존 B트리처럼 leaf에 key를 추가하면 된다. Case 2. key값이 overflow되는 경우: 1. overflow된 노드의 중간을 기준으로 2개로 나눈다. 이때, 기준이 되는 곳은 나눈 노드의 오른쪽에 ..

B-트리 B-트리는 스스로 균형을 맞추는 자가 균형 이진 트리의 확장판이다. 기존 이진 트리와 다른 점은, 한 노드에서 여러 개의 데이터를 가진다는 점이다. B트리는 탐색, 삽입, 삭제 모두 O(log N)의 시간복잡도를 가진다. 주로 디스크와 같은 물리저장소에서 빠르게 접근하기 위해서 사용된다. B트리는 다음과 같은 특징을 가진다: 1. 노드의 key 수가 k개이면, 노드의 자식은 k+1개여야 한다. 2. 노드의 key는 정렬되어야 한다. 3. 자식 노드의 key는 현재 노드의 key를 기준으로 나뉜다. 4. root 노드는 2개 이상의 자식노드를 가진다.(단, root 노드가 leaf인 경우에는 제외)\ 5. M차 트리일 때, 노드가 가질 수 있는 key값은 floor(M/2)-1부터 M-1개까지 가..