B-트리 썸네일형 리스트형 Deletion On B-Tree 1 B-트리에서의 삭제는 삽입과 유사하나 이보다 조금 더 복잡하다. 이는 리프(leaf) 노드만이 아닌, 임의의 노드에서 키가 삭제될 수 있으며, 내부 노드에서의 삭제는 자식 노드들에 대한 재배열을 요구하게 되기 때문이다. 삽입에서의 삭제 시에도 B-트리의 특성에 위반되는 구조를 갖는 트리가 만들어지는 것을 방지할 수 있어야 한다. 삽입 때문에 한 노드가 너무 커지지 않도록 보장하는 것처럼, 삭제로 인해 한 노드가 너무 작아지지 않는 것을 보장할 수 있어야 한다(루트 노드가 최대 2t - 1개를 초과하는 키들을 갖는 것이 허용되지 않더라도 루트 노드는 최소 t - 1개 미만의 키를 갖는 것이 혀용되는 것만 제외하면). 간단한 삽입 알고리즘에서 키가 삽입될 경로 내의 노드가 이미 가득 찬 경우 되돌아 가야 할.. 더보기 각 B-트리 구현에서의 차이점 B-트리(tree)의 노드에서 키의 중복을 허용할 것인지, 허용하지 않을 것인지에 따위와 같은 세부 구현은 조금씩 다르다. 일반적으로, 중복되는 키 값은 오류가 발생할 확률이 높고, 공간도 낭비하는 경향이 있다. 그러나, B-트리에서는 이야기가 조금 다른데, B-트리가 한번에 읽어들이는 페이지에서 어떤 키 값을 찾았다고 해보자. 그러나, 이 키 값이 실제 값을 저장하고 있는 것이 아니라 실제 값을 저장하고 있는 다른 노드로의 포인터만 가지고 있다면, 이 페이지를 버리고 해당 페이지를 다시 읽어들어야 하는 낭비가 뒤따른다. 따라서, B-트리의 일반적인 구현에서는 이런 키의 중복을 허용하기도 한다. 또, 키의 상승(promotion)에 있어서 어떤 값을 상위 단계로 올리는지도 조금씩 다르다. 어떤 값이 노드.. 더보기 B-트리 용어의 유래 .... 기초적인 B-트리(tree) 알고리즘의 변형과 성능을 논하기 이전에, B-트리 용어를 좀 더 형식적으로 기술하는 것이 필요하다. 차수(order)나 리프(leaf) 등과 같은 용어의 철저한 정의를 제공하는 것은 B-트리로 구분되기 위해 자료구조가 지녀야만 하는 성질을 설명할 수 있도록 한다. 다시 말해, B-트리의 성질에 대한 이러한 정의는 B-트리로부터 키를 삭제하는 절차와 같은 문제에 대한 논의를 할 수 있도록 한다. 불행하게도, B-트리에 관한 문헌은 B-트리와 관련된 용어를 이용하는데 있어 동일하지 않다. 그러므로 문헌을 읽고 새로운 개발을 하는 것은 약간의 융통성과 예비 지식을 필요로 한다. 독자는 기본적인 용어의 다른 사용에 대해서도 알 필요가 있다. 예를 들어, Bayer와 McCr.. 더보기 이전 1 다음