[Database System] B+ Tree Index

Summay Of Last Class

Hash Table은 모든 DBMS에서 이용되는 중요한 data structure로, O(n)의 공간 복잡도와 O(1)의 시간 복잡도를 가진다.

 

B+ Tree

B+Tree란 self-balancing을 진행하는 정렬된 tree data로, search, sequential access, insertions, 그리고 deletions를 모두 O(logn) 에 처리한다.

 

이는 좀 더 일반화된 binary search tree라고 할 수 있는데, node가 둘 이상의 children을 가질 수 있기 때문이다.

 

B+ Tree는 large blocks of data를 대상으로 한 read-wrtie에 최적화 되어있다.

 

B+ Tree Properties

B+ Tree는 다음의 특성을 만족하는 `M-way serach Tree`에 해당한다.

 

1. perfectly balanced: 모든 leaf node는 tree에서 같은 depth를 갖는다.

2. 각 노드는 M/2 -1 이상, M-1 이하의 key를 포함한다.

3. k개의 키를 가진 노드는 k+1개의 자식을 가진다.

 

Nodes

B+ Tree의 모든 node는 key/value 페어를 담은 array로 이루어져있다.

 

일반적으로 key는 index가 기반으로 하는 attribute을 통해 얻게 된다.

value의 경우 node가 inner node인지, leaf node인지에 따라 달라지게 된다.

 

array는 일반적으로 key를 sorted order로 관리하게된다.

 

모든 NULL key는 first, 혹은 last leaf node에 저장된다.

 

 

B - Tree vs B + Tree

B - Tree의 경우 tree에 존재하는 모든 node에 key-value를 저장한다.

중복키를 허용하지 않기 때문에, more space-efficient 하다.

 

반면 B+ Tree의 경우 value는 leaf nodes에만 저장하며, Inner node의 경우 search process를 돕기 위한 guide 정보를 제공한다.

B+ Tree의 경우 data가 leaf node에만 저장되므로 Insertion과 Deletion에서 B-Tree에 비해 쉽다는 장점이 있다.

 

B+ Tree - Insert

B+ Tree는 다음과 같이 Insert를 진행한다.

 

1. correct leaf node L을 찾는다.

 

2. L에 정렬된 순서로 data를 Insert한다.

 

3. 만약 L이 충분한 공간을 가지고 있다면, 작업을 완료한다. 만약 L에 충분한 공간이 없다면 다음 작업을 수행한다.

 

4. L key를 L와 새로운 node L2로 split 한다.

   이 때, 첫 번째 node는 ceil((m-1)/2) 개의 value를 가지며, 두 번째 node는 남은 value를 갖게 된다.

   이후, 새로 생성된 node의 가장 작은 key value를 parent node로 복사한다.

   만약 parent node, 즉 non-leaf node에서 overflow가 발생하면 아래 과정을 수행한다.

 

5. non-leaf node를 2 node로 분할한다.

    첫 번째 node는 ceil(m/2)-1 의 값을 contain한다.

    첫 번째 node에 배정한 후, 남아 있는 값 중 가장 작은 값을 parent에게 배정한다.

    두 번째 노드는 남은 keys를 contain한다.

 

B+ Tree - Delete

1. root에서 출발해서, target entry를 포함하고 있는 leaf L을 찾는다.

 

2. 해당 entry를 제거한다.

 

3. 만약 L이 최소 half-full을 충족한다면, 동작을 완료한다. 만약 그렇지 않다면 아래 과정을 수행한다.

 

4. sibling(L과 같은 parent를 가진 adjacent node) 에게서 half-full을 충족하기 위해 borrow를 진행한다.

    이를 `re-distribute`라고 하는데, re-distribute가 실패하면 L와 sibling을 `merge`하는 방식으로 처리한다.

    만약 merge가 수행되면, parent of L에서 L 또는 sibling을 pointing하는 entry를 제거한다.

 

 

B+ Tree - Duplicate Keys

B+ Tree는 insert, delete 등에 대해 항상 O(logn) Time에 동작해야 한다.

따라서 Duplicated Keys를 처리하는 것은 매우 중요한 문제인데, 별 다른 처리 없이 Duplicated Keys를 허용하면 insert 등의 연산의 시간 효율성에 부정적인 영향을 미치기 때문이다.

 

Duplicated Keys를 처리하는 방법에는 `Append Record ID`, `Overflow Leaf Nodes` 방법이 존재한다.

다만 Overflow Leaf Nodes의 경우 O(logn) 접근을 위반하는 처리방법이다.

 

Append Record ID

Tuple에 unique한 RecordID를 추가하여, 모든 key가 Unique하게 만드는 방식이다.

위와 같이 중복된 Key가 담길 수 있으며, RecordID를 사용하여 개별적으로 식별이 가능하다.

 

Overflow Leaf Nodes

위와 같이, 중복키로 인한 Overflow가 발생 시 Overflow nodes를 생성하고, 중복된 키를 contain한다.

 

Record ID를 저장하지 않아도 된다는 장점이 있지만, B+ Tree의 장점인 logn 처리 시간을 위반할 수 있다는 큰 단점이 있다.

 

 

Index

Index란 disk-based structure로, table 또는 view와 연결되어 빠른 row 검색을 가능하게 한다.

Table 혹은 view의 table, view's column은 index 에서 key를 생성하기 위해 사용된다.

이러한 key는 앞서 설명한 B-Tree나 B+Tree에 저장되며, SQL Server가 빠르고 효율적으로 row에 접근할 수 있도록 도와준다.

Clustered Indexs

Clustered Index에서 table은 primary key를 기준으로 sort되어 저장된다.

 

Clusted Index를 생성하기 위해서는 아래와 같은 조건을 만족해야 한다.

 

1. data의 sequential 또는 sorted order

 클러스터형 인덱스를 사용하려면 테이블의 데이터(레코드)가 순차적이거나 정렬된 순서로 저장되어 있어야한다. 이는 테이블의 레코드가 특정 열(Primary key가 주로 사용된다)을 기준으로 정렬되어 있어야 한다는 것을 의미한다.

데이터는 인덱스의 키 순서대로 저장된다.

 

2. Unique한 키 값

클러스터형 인덱스의 키 값은 중복되지 않아야 한다. 즉, 각 레코드에 대한 키 값은 고유해야 한다. 이는 주로 테이블의 기본 키(primary key) 열을 기반으로 한다.

 

MySQL과 같은 일부 DBMS들은 항상 clustered index 방식으로 동작한다.

 

이러한 방식의 장점은, 우리가 scan을 진행할 때 sequential한 접근에 대한 효율성이 매우 높아진다는 것이다.

반면, insert 등의 동작마다 정렬을 수행해야 하므로 해당 동작에서는 Non-Clustered 방식에 비해 성능이 떨어진다.

 

Non-Clustered Indexs

Clustered Index와 반대로, 지정된 Column에 대한 물리적인 re-order를 수행하지 않는다.

 

 

leaf node는 정렬되어 있지만, 실제로 leaf node가 pointing하는 위치는 random이 될 수 있다.

따라서 위와 같은 굉장히 비효율적인 Page 탐색이 발생할 수 있고, 이는 read 작업 속도를 굉장히 느리게 만든다.

 

Non-clustered Index의 경우 Insert, Update, Delete 등의 속도가 빠르지만, Sequential Read가 매우 느리다는 단점이 있다.

 

 

Merge Threshold

일부 DBMS의 경우 node가 half full 인 경우 merge를 수행하지 않는다.

 

왜냐하면 merge operation을 delay하는 것은 reorganization에 들어가는 상당한 비용을 아낄 수 있기 때문이다.

 

또한 조건을 충족하지 못하는 작은 node를 그대로 두고, 주기적으로 전체 tree를 rebuild하는 것이 비용적인 측면에서 이득인 경우도 존재한다.

 

이는 PostgreSQL이 구현하고 있는 B+ Tree를 non-balanced B+ Tree라고 부르는 이유에 해당한다.