b-tree 썸네일형 리스트형 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.. 더보기 Introduction to B-Tree 2 효율적인 트리(tree) 구조를 유지하는데 가장 큰 문제는, 최적의 트리 탐색 성능을 제공하기 위해서 트리는 정렬된 상태로, 균형 트리를 이루어야 한다는 것이다. 그러나 트리의 균형을 잡는 연산은 매우 비싸다. 이진 트리가 이상적인 상태를 유지한다고 하더라도, 이진 탐색은 디스크 상주 인덱싱에 비해서 그다지 빠르지 않다. 트리가 최적의 탐색 성능을 제공하기 위해서는, 트리는 균형을 이루어야 하는데, 이것은 가능한 한 루트에서 가장 끝에 위치한 각각의 노드까지 경로가 최대한 비슷해야 한다는 것을 의미한다. 즉, 트리가 최악의 성능을 보이는 경우는 일렬로 노드가 연속되어 붙어 있을 때이며, 이 경우 사실 트리라기보다는 리스트에 더 가깝다. 역사적으로 트리를 균형 상태로 유지하기 위해 AVL 트리나, 페이지화.. 더보기 Introduction to B-Tree 1 가변 길이 레코드 집합을 탐색하기 위해 인덱스(index)를 사용하는 것은 효과적인 기법이다. 그러나, 문제는 인덱스 전체를 메모리에 올릴 수 없는 경우이다. 이 문제를 해결하기 위해, 1972년 Bayer와 McCreight가 발표한 논문의 처음 몇 단락을 보기로 하자. 여기에서는 그들이 B-트리(B-Tree)로서 해결하고자 했던 문제, 즉 메모리로 적재하기에는 너무 큰 인덱스의 접근과 유지에 관한 방법에 대해 간결하게 설명하고 있다. .... 이 논문에서는 동적으로 변화하는 임의 접근 파일(random access file)을 위해서 인덱스를 구성하고 유지하는 문제에 관해 고찰한다. 여기서 인덱스라 함은 물리적으로 인접한 고정된 크기의 두 데이터 항목, 즉 키(key) x와 관련 정보 a가 갈협하여 .. 더보기 이전 1 다음