목록2-3-4트리 (1)

넘치게 채우기

[자료구조] 4-11. B+트리와 B*트리, 2-3-4 트리

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개로 나눈다. 이때, 기준이 되는 곳은 나눈 노드의 오른쪽에 ..
컴퓨터과학/자료구조 2023. 4. 16. 18:39
이전 Prev 1 Next 다음