BTREE
-
자료구조 - BTreeCS/자료구조 2021. 2. 22. 19:28
B-Tree B-tree B의 의미는 balance를 의미한다. 군형잡힌 다진검색트리로 다음의 성질을 만족한다. (다진검색트리란 자식을 여러개 갖는 트리를 말한다.) 루트 제외 모든 노드는 최소 k/2 ~ k개의 키를 갖는다. 모든 리프노드는 같은 깊이를 갖는다. 디스크에 저장하는 cost를 최소화하여 데이터베이스에서 주로 사용된다. 최악의 경우 디스크 접근 횟수를 줄일 수 있다. B-tree의 삽입 삽입 후 오퍼플로우가 발생하면(키의 수가 k보다 많으면) 형제 노드(양 옆의 노드) 중 여유가 있는 노드가 있으면 남는 키를 형제 노드에게 삽입해 준다. 없으면 오버플로가 발생한 레코드를 둘로 분할하고 가운데 키를 부모 노드로 넘긴다. B-tree의 삭제 삭제 후 언더플로우가 발생하면(키의 수가 k/2보다 ..