본문 바로가기

Library/File Structure

B* Tree 1973년 Knuth는 삽입 시의 재분개 개념에 분할에 대한 새로운 개념을 포함하도록 확장하였다. 그는 이 트리를 B* 트리(tree)라 명명했다. 재분배를 통해 분할을 연기하는 시스템을 생각해보자. 루트(root) 페이지 이외의 페이지를 고려한다면 그 페이지가 분할될 때는 이것이 적어도 꽉 찬 형제(sibling)를 하나 가진다는 것을 알고 있다. 이것은 기존에 한 페이지를 둘로 나누는 방법보다 둘을 셋으로 나누는 방법의 가능성을 제시한다. 두 페이지를 셋으로 분할하는 방법은 분할된 페이지가 반으로 차기보다는 2 / 3 정도로 찬다는 중요한 측면을 가진다. B* 트리는 다음과 같은 성질을 가진다. 1. 각 페이지는 최대 m 개의 자손을 가진다. 2. 루트 노드와 리프(leaf) 노드를 제외한 각 페이지.. 더보기
B-Tree Variant : B+ Tree, B* Tree B-트리(tree)는 제한된 메모리 공간에서 인덱스를 다룰 수 있는 유용한 수단이지만, 다른 전략과 마찬가지로 단점이 존재한다. 대표적으로, 다음과 같은 문제를 들 수 있다. 1. 각각의 노드의 공간 활용성이 낮다 : B-트리의 리프(leaf) 노드들은 일반적으로 최대 차수가 n이라 했을 때 n / 2 정도의 키 값만 저장하고 있다. 대체적으로 각 노드의 공간 활용도는 50%이다. 2. 순차 탐색을 지원하지 않는다 : 쿼리(query)는 프라이머리 키(primary key)로 주어져야 하며, 세컨더리 키(secondary key)로 주어지는 쿼리에 대해서 복수의 레코드를 탐색해야 하는 경우, 각 레코드를 검색할 때마다 루트에서부터 검색을 시작해야 한다. 3. 복수의 레코드 얻기 : 세컨더리 키로 각 레코.. 더보기
Deletion On B-Tree 2 B-트리(tree)에서의 삽입과 삭제는 모두 리프(leaf)에서의 변경이 위로 전파(propagate)된다는 것이 중요하다. 만약, 루트에서 키를 하나만 가지고 있고, 이 키 값에 대한 삭제가 일어난다면 단지 하나만 제거하고, 그것으로 그만이다. B-트리의 구현은 여러가지가 있으며, 여기서의 삭제 연산도 그런 구현 중 하나이다. 구체적으로, 여기서의 삭제 연산은 키의 중복을 허용하는 버전의 경우이며, 노드에서의 차수(order)는 하나의 노드가 가질 수 있는 자손(decendant)의 최대 개수를 의미한다. 이 버전에서 노드 n에서 키 k를 삭제하는 규칙은 다음과 같다. 1. 만약 n이 키의 최소 개수 이상이고, 키가 n에서 가장 크지 않다면, 간단히 n에서 k를 삭제한다. 2. 만약 n이 키의 최소 개.. 더보기
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 3 B-트리는 삽입과 삭제의 선형 비용 문제를 해결하는 다단계 인덱스이다. 이것이 B-트리가 좋은 이유이고, 인덱스를 표현하는 표준 방법이 된 이유이다. 해결 방법은 두 부분으로 나뉜다. 첫 번째는 가득 차게 될 인덱스 레코드를 요구하지 않는다. 두 번째는 다음 레코드로 오버플로우(overflow) 키를 넘기지 않는다. 대신 초과되는 레코드를 두개의 인덱스 레코드로 각각 반씩 나눈다. 삭제는 필요할 때 인덱스를 하나의 레코드로 합치는 전략을 취한다. B-트리의 각각의 노드는 인덱스 레코드이다. 이 레코드의 각각은 B-트리의 차수(order)라고 불리는 키-참조 쌍의 최대수를 가질 수 있다. 또한 보통 차수의 반인 최소소의 키-참조 쌍을 가질 수 있다. 차수가 100인 B-트리는 레코드 당 최소 50개의 키와.. 더보기
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가 갈협하여 .. 더보기
Cosequential Processing Cosequential Processing이란, 2개 이상의 리스트를 입력으로 받아서, 각각의 리스트에 대해 선형적인 작업을 한 뒤 단일한 하나의 출력을 내는 것을 말한다. 왜 이런 작업이 필요한 것일까? 예를 들어, 현재 사용 가능한 메모리보다 다루어야 하는 데이터가 훨씬 크다면, 어쩔 수 없이 분할된 형태로 읽어들일 수 밖에 없을 것이다. 그러나, 만약 전체 데이터에 대해 정렬 작업을 해야 한다면 이것은 복잡한 문제가 된다. 어떤 정렬 알고리즘은 데이터 전체가 메모리에 올려져 있어야 하며, 전체 데이터의 일부분만 메모리에 올려져 있는 이와 같은 경우, 그러한 알고리즘은 사용할 수 없다. 즉, 전체가 아닌, 각각의 분할에 대해 작업을 한 뒤 그것을 합쳐서 하나의 완전한 형태의 출력물을 내야 하는데, 그.. 더보기

티스토리툴바