목록자료구조 (1)

Haneul's Blog

[자료구조] B-tree와 B+tree에 대해 알아보자!

B-tree..? 만약 자료구조를 공부하지 않았더라도 DB를 공부한 적이 있는 분들이라면 들어본 적이 있는 자료구조일 것입니다. B-tree란? B-tree는 DB의 인덱스에서 사용되는 자료구조로 이진트리를 확장해서 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 쉽게 말해 하나의 노드에 여러 자료가 배치될 수 있는 트리 구조라고 할 수 있습니다. 그리고 Balanced Tree라는 특징이 있는데, 이는 노드 삽입 및 삭제 시에 스스로 균형을 맞춰주는 트리를 의미합니다. 기존 이진트리의 경우에는 좌우 균형이 맞지 않는 편향 트리가 생길 수도 있는 문제점이 있어 최악의 경우에 O(n)이라는 시간 복잡도를 가져서 검색 효율이 떨어지는 경우가 생깁니다. Balanced Tre..
자료구조 2022. 10. 6. 18:16
이전 Prev 1 Next 다음