[Database] 인덱스 (Index) 3장 : B+-Tree Index 기본

 

https://kghworks.tistory.com/150

[Database] 인덱스 (Index) 2장 : Ordered Index

 

 2장 Ordered Index에서 B+-Tree를 언급하지 않았다. B+-Tree Index는 가장 흔히 쓰이는 인덱스로 설명할 양도 많다. 이번에는 포스팅 2개에 걸쳐 B+-Tree Index의 기본과 확장에 대해 정리해보려 한다. 

 

B+-Tree 예시

 

목차

• B+-Tree Index 의 필요성과 기본 구조
• B+-Tree Index를 활용해서 Query
• B+-Tree 수정하기
• 복잡도
  Nonunique Search Key

---

B+-Tree Index 의 필요성과 기본 구조

Dense Index 예시

 

 일반적인 Oredered Index는 Index의 구조 자체가 커지면 Index의 Access time이 증가한다. Index 구조상 한쪽에서부터 탐색을 시작하는데 찾고자 하는 값이 인덱스 정중앙의 값이라면 어떻게 될까. 정중앙의 값을 찾는 속도는 인덱스의 구조가 커질수록 비례하여 저하될 것이다. 인덱스를 재구조화할 수 있지만 재구조하는 작업 빈도가 많아지면 Insertion time, Deletion time이 증가한다. 

 이에 따라 file이 커져도 Access time을 보장할 수 있는 B+-Tree Index가 등장했다. 

 

B+-Tree 인덱스 기본 구조

B+-Tree 예시

 

 Access time을 보장하면서 동시에 재구조화 작업이 다른 Orederd Index에 비해 간단하다. 따라서  Access time을 보장하고, Insertion time, Deletion time도 보장하는 인덱스이다. (그럼에도 File 수정 시 Insertion time, Deletion time, Space overhead는 존재) 가장 널리 사용되는 인덱스이다. 

 구조는 이진 균형 트리 (balanced tree)로서 모든 단말 노드 (leaf node)에 대한 root node로부터의 탐색 속도가 같다. Tree이니 level이 있으므로 당연히 Multilevel Index에 속한다.

 

B+-Tree 노드 구조 

B+-Tree 노드 예시

• n (fanout) : 노드 내 최대 pointer 개수
• K : search key 값, (n-1) 개, K1, K2, ..., K(n-1)
• P : search key node의 pointer, P1, P2, ..., Pn

 

 루트 노드 (Root nodes)는 최소 2개이상 최대 n/2개의 pointer를 가질 수 있다. pointer Pi는 Ki 보다 작은 search key들이 있는 서브트리를 가리킨다.

 

내부 노드 (Intternal nodes)

 내부 노드의 모든 pointer는 서브 트리를 가리킨다. fanout이라는 개념이 등장하는데 fanout이란 내부 노드 하나에 들어갈 수 있는 pointer 개수이다. B+-Tree의 fanout이 4라면 이 B+-Tree의 노드 하나당 4개의 pointer, 3개의 search key가 들어갈 수 있다. (이번 예시처럼)

어떤 노드의 Pi가 가리키는 서브트리의 모든 search key는 Ki보다 작고 K(i-1) 보다 같거나 크다. 위 예시에서 Gold가 속한 내부노드의 P2가 가리키는 서브트리의 모든 search key는 K3(Gold) 보다 작고 K2(Einstein) 보다 같거나 큰 것을 확인할 수 있다. 

 아래 n=6인 B+-Tree index의 단말노드를 제외한 예시이다.

 

n=6인 B+-Tree의 비단말 노드를 제외한 예시

단말 노드 (Leaf nodes)

leaf node 예시

 가장 마지막 노드인 leaf node는 실제 file을 가리키는 포인터를 가진다. 그리고 단말 노드의 가장 마지막 노드 (Pn)는 옆에 위치한 단말 노드의 첫 번째 포인터 (P1)을 가리킨다. 형제가 아니어도 옆에 위치한 단말 노드를 가리키고 있다. 따라서 최대 n-1 (n = fanout) 개의 record를 가질 수 있다.

Dense index라면, 모든 Leaf node는 모든 record를 가리키고 있어야 한다. (모든 record에 대한 인덱스가 필요하므로) 

---

B+-Tree Index를 활용한 Query

 B+-Tree 탐색은 루트 노드부터 시작한다. 찾으려는 search key v를 가진 단말 노드를 찾을 때까지 반복적으로 탐색한다. 아래는 pseudo code이다. 

/* search key v를 가진 단말노드를 찾는 함수 (unique search key) */

/* 중복 search key는 없다고 가정 and returns pointer to the record with
* 찾으려는 record의 pointer를 return (없으면, return null)*/
function find(v)

	/* 루트 노드 찾음 */	
    Set C = root node
    /* 단말노드를 찾을 때까지 반복 */	
    while (C is not a leaf node) begin
      /* v보다 큰 search key 중 가장 작은 search key */
      Let i = smallest number such that v ≤ C.Ki
      
      /* 없으면, 해당 노드의 가장 마지막 not null pointer로 이동*/
      if there is no such number i then begin
          Let Pm = last non-null pointer in the node
          Set C = C.Pm
      end
      /* 있고, 찾으려는 search key이면, i+1 pointer로 이동 */
      else if (v = C.Ki) then Set C = C.Pi+1
      /* 아니면, i pointer로 이동 */
      else Set C = C.Pi 
end

if for some i, Ki = v
    then return Pi /* return pointer */
    else return null ; /* return null, record 없음*/

 

예시로 search key Katz를 탐색해 보자

 

1. 로트 노드 : Katz보다 큰 search key 중 가장 작은 search key? K1
2. P1으로 이동 (Katz < Mozart)
3. 내부 노드 : Katz보다 큰 search key중 가장 작은 search key? 없음
4. 해당 노드의 가장 마지막 not null pointer P3로 이동
5. 단말 노드 : Katz가 있다면 해당 node의 pointer로 record 탐색 완료 (P2)

 

range query

 search key의 범위를 주어 query 하는 것을 range query라 한다. (e.g. 20 < search key age < 31 인 record 탐색) range query도 기본 동작은 비슷하다. 먼저 범위의 최솟값의 search key 단말 노드를 탐색한다. (search key가 20인 단말 노드) 그다음 범위에 해당하는 모든 pointer를 수집하는 과정이 추가된다. 아래는 pseudo code이다. 

 

/* search key lb ≤ V ≤ ub 를 만족하는 모든 V 에 대한 pointer 반환 */
function findRange(lb, ub)

    Set resultSet = {};
    Set C = root node
    
    /* search key에 해당하는 최솟값 leaf node 탐색 */
    while (C is not a leaf node) begin
        Let i = smallest number such that lb ≤ C.Ki
        if there is no such number i then begin
            Let Pm = last non-null pointer in the node
            Set C = C.Pm
        end
        else if (lb = C.Ki) then Set C = C.Pi+1
        else Set C = C.Pi
    end
    
    /* 최솟값 leaf node가 없으면,  */
    Let i be the least value such that Ki ≥ lb
    if there is no such i
        then Set i = 1 + number of keys in C; 
        
    Set done = false;
    
    /* 최솟값 leaf node 부터 범위에 해당하는 모든 pointer 수집 */
    while (not done) begin
        Let n = number of keys in C.
        if ( i ≤ n and C.Ki ≤ ub) then begin
            Add C.Pi to resultSet
            Set i = i + 1
        end
        else if (i ≤ n and C.Ki > ub)
            then Set done = true;
        /* 다음 leaf로 이동 */
        else if (i > n and C.Pn+1 is not null)
            then Set C = C.Pn+1, and i = 1 
        /* 종료 */
        else Set done = true; 
    end
    return resultSet;

 

B+-Tree 비용

 단말 노드를 찾는데 access 하는 노드의 개수는 최대 log(n/2)^(N) (N = 전체 record 수)이다. 만일 n (fanout)이 100이고, 전체 record 수가 1백만 개일 때는 최대 4개의 노드를 access 하여 단말 노드를 탐색한다. (log50^1,000,000) 

 

일단 단말 노드를 찾았다면, record를 fetch 하기 위한 random I/O operation이 추가된다. range query라면 Nonclustered Index일 때, 범위에 해당하는 모든 record를 fetch 하는 random I/O operation이 필요하다. 

---

B+-Tree 수정하기

 B+-Tree는 의 수정에는 크게 DELETION(삭제), INSERTION(삽입)가 있다. UPDATE의 경우 인덱스 엔트리를 DELETE & INSERT 하므로, DELETION와 INSERTION만 알아본다. 

 먼저 수정 작업에서 사용되는 액션은 2가지 split (분할), coalesce (병합)이다. split은 인덱스 수정 결과 노드의 최대 크기(fanout)를 넘어섰을 때 노드를 분할하는 것을 말한다. coalesce는 노드의 크기가 너무 작을 때 인접 노드와 병합하는 것을 말한다. 

 

INSERTION (삽입)

 앞에서 본 pseudo code find(v)와 동일하게 동작한다. find(v)로 search key를 가진 단말 노드를 찾아 해당 노드에 Index entry를 삽입한다. 만약, 삽입한 결과 split이 필요해지면 부모 쪽으로 순차적으로 탐색해 가며 split이 더 이상 일어나지 않는 노드에 도달할 때까지 split을 반복해 나간다. 최악의 경우 root 노드까지 모든 경로의 부모를 split 하고 B+-Tree height이 1 증가될 수 있다. 

 

search key "Adams" 삽입 전

만약 위 트리에서 search key가 Adams인 인덱스를 삽입하면 아래와 같은 결과가 나온다. 

 

search key "Adams" 삽입 후

이번엔 split이 발생할 수 있는 경우를 알아보자. 만일 위 트리에서 ("Adams" 삽입 후) "Lamport" search key를 삽입하면 어떻게 될까. 

search key "Lamport" 삽입 후

 

  "Lamport"가 삽입되어야 할 단말 노드의 사이즈가 이미 가득 찼기 때문에 split이 발생했다. 부모 노드가 생성되면서 level 1에 있던 Gold는 루트 노드로 올라갔다.  INSERTION pseudo code는 아래와 같다.

 

/* 단말 노드에 삽입 
* L : 단말 노드, K : search key, P : pointer */
procedure insert_in_leaf (node L, value K, pointer P)
    if (K < L.K1)
        then insert P, K into L just before L.P1
        else begin
        Let Ki be the highest value in L that is less than or equal to K
        Insert P, K into L just after L.Ki
    end

/* 비단말 노드에 삽입 
* N : N, N`를 포함하는 노드, K` : N`의 search key, N` : 생성된 right hand side 노드 */
procedure insert_in_parent(node N, value K′, node N′)
    if (N is the root of the tree)
        then begin
            Create a new node R containing N, K′, N′ /* N and N′ are pointers */
            Make R the root of the tree
            return
        end
    Let P = parent (N)
    if (P has less than n pointers)
        then insert (K′, N′) in P just after N
        else begin /* Split P */
            Copy P to a block of memory T that can hold P and (K′, N′)
            Insert (K′, N′) into T just after N
            Erase all entries from P; Create node P′
            Copy T.P1 …T.P⌈(n+1)∕2⌉ into P
            Let K′′ = T.K⌈(n+1)∕2⌉
            Copy T.P⌈(n+1)∕2⌉+1 …T.Pn+1 into P′
            insert in parent(P, K′′, P′)
        end

 

DELETION (삭제)

삭제는 좀 더 복잡하다. 먼저 삭제 대상 search key를 위 find(v) 알고리즘으로 탐색한다. 그다음 underfull이 발생하면, coalesce를 실행해 노드를 재분배(redistribute)한다. underfull이란 한 노드의 pointer 수가 n/2보다 작은 것을 말한다. underfull이 발생하면 underfull을 해결하기 위해 전체 재배치하는데 이를 재분배(redistribute)라고 한다. 

 

 

"Srinivasan"를 삭제한다면,

 

search key "Srinivasan" 삭제 전

search key "Srinivasan" 삭제 후

1. 단말 노드에서 "Srinivasan" search key, pointer 제거
2. underfull  : 단말 노드에 발생 pointer 1개
3. coalesce : 형제 노드와 병합
4. 부모 노드에서 삭제된 노드를 가리키는 pointer 제거
5. underfull : 부모노드에 pointer 1개
6. coalesce 불가능 : 형제 노드에 "Califieri", “Einstein”, “Gold” 로 꽉 차있음
7. redistribute : underfull 발생 안 하도록 형제노드와 재분배

 

 부모노드에서 redistribute 작업 중 형제 노드의 "Gold"가 루트노드로 이동하고, 기존 루트노드의 "Mozart"가 내려온 것을 볼 수 있다. 만약 루트노드에 "Moazrt"를 그대로 두고 "Gold"가 병합되어 들어왔다면 B+-Tree 순서가 맞지 않기 때문이다 ("Gold" < "Mozart")

 

 

이번에는 "Gold"를 제거해 본다.

 

search key "Gold" 삭제 전

search key "Gold" 삭제 후

 

1. 단말노드에서 "Gold" 제거
2. underfull  : 단말 노드에 발생 pointer 1개
3. coalesce : 형제 노드와 병합
4. 부모 노드에서 삭제된 노드를 가리키는 pointer 제거
5. underfull : parent node에 pointer 1개, 루트 노드에 pointer 1개
6. coalesce : 루트노드의 "Gold"를 내리면서 형제와 병합
7. 루트노드 제거 : 루트노드는 2개 이상의 pointer를 가져야 함

트리의 높이가 -1 되었다. 그리고 루트 노드에 search key "Gold"는 여전히 남아있다.

 

아래는 DELETION pseudo code다.

 

/* k : search key, P : pointer */
procedure delete(value K, pointer P)
    find the leaf node L that contains (K, P)
    delete entry(L, K, P)

/* N : node k : search key, P : pointer
* 특정 노드 N의 search key k와 pointer P를 제거하는 함수*/
procedure delete entry(node N, value K, pointer P)

	/* search key, pointer 제거 */
    delete (K, P) from N
    
    /* 루트노드이고, pointer가 1개이면, 루트노드를 제거하고, child를 루트노드로*/
    if (N is the root and N has only one remaining child)
    then make the child of N the new root of the tree and delete N
    
    /* 노드가 underfull이라면, 노드를 형제로 병합, search key는 이전노드와 병합 노드 사이를 구분*/
    else if (N has too few values/pointers) then begin
        Let N′ be the previous or next child of parent(N) /* N′은 N의 형제 노드 */
        Let K′ be the value between pointers N and N′ in parent(N) /* K′는 N과 N′ 사이의 search key */
        
        /* 병합 : 병합해도 노드 크기를 넘지 않을 때 */
        if (entries in N and N′ can fit in a single node)
            then begin /* Coalesce nodes */
                if (N is a predecessor of N′) then swap_variables(N, N′)
                if (N is not a leaf)
                    then append K′ and all pointers and values in N to N′
                    else append all (Ki, Pi) pairs in N to N′; set N′.Pn = N.Pn
                delete entry(parent(N), K′, N); delete node N
            end
            
        /* 재분배 : 이웃노드 N′로부터 search key를 가져옴 */
        else begin 
            if (N′ is a predecessor of N) then begin
                if (N is a nonleaf node) then begin
                    let m be such that N′.Pm is the last pointer in N′
                    remove (N′.Km−1, N′.Pm) from N′
                    insert (N′.Pm, K′) as the first pointer and value in N,
                        by shifting other pointers and values right
                    replace K′ in parent(N) by N′.Km−1
                end
                else begin
                    let m be such that (N′.Pm, N′.Km) is the last pointer/value
                        pair in N′
                    remove (N′.Pm, N′.Km) from N′
                    insert (N′.Pm, N′.Km) as the first pointer and value in N,
                        by shifting other pointers and values right
                    replace K′ in parent(N) by N′.Km
                end
            end
            else … symmetric to the then case …
        end
    end

---

복잡도

B+-Tree의 수정 복잡도는 log(n/2)^N (n =fantou, N = record 수)이다. Deletion도 마찬가지다. 성능은 B+-Tree의 높이에 비례한다. 실제로는 최악보다는 좋은 성능을 보인다. relation의 크기가 아주 커도 대부분의 비단말 노드가 메모리 버퍼에 있을 가능성이 높기 때문이다. 평균적으로 수정에 대해서는 1번의 I/O Operation이 필요하게 된다.

 또한 underfull을 계속 감지하여 노드별 최소 50% 이상의 포인터가 저장된 걸 보장하기 때문에 space overhead도 어느 정도 확보한다. 

 nonunique search key에 대해서는 조금 다른데, 바로 다음에 다룬다. 

 

---

Nonunique Search Key

 말 그대로 search key가 unique 하지 않은 것을 말한다. 이를테면, 학생 relation에 학생_이름 속성을 search key로 인덱스를 생성했다면, 이 search key는 중복을 허용하게 된다. (동명이인) 그러나 실제로 DBMS는 unique하지 않은 속성에 대해 인덱스를 생성할 때, 다른 unique 속성을 추가하여 복합 인덱스를 생성한다. 만약 학생 이름 속성으로 인덱스를 생성한다면, <학생+이름, 학생 식별자(PK)> 의 조합으로 인덱스를 생성하는 식이다. 

 

B+-Tree 인덱스에서 중복 search-key를 유지하면서 사용하는 방법

 성능은 별로지만 중복을 허용하는 방법도 있다. 이때는 search key는 트리에 unique 하게 저장하고, 각 search key가 pointer bucket (list)를 유지한다. 만약 학생_이름 속성으로 인덱스를 생성했다면 "Karnia"인 인덱스 엔트리에 (학생_이름 = 'Karina')인 모든 record를 가리키는 pointer를 bucket에 담아 저장하는 식이다. 

 일단 트리 구현이 복잡해진다. 동적으로 bucket size를 유지하기 위한 추가 코드가 필요해진다. bucket이 너무 커지면, bucket을 별도 block에 저장해야 할 수 있다. (추가 I/O Operation) Unique search key에 비해 DELTION 성능도 떨어진다. 특정 search key에 대한 하나의 pointer를 제거하기 위해 pointer bucket을 모두 탐색해야 하기 때문이다. 

 그렇기 때문에 대부분의 DBMS는 자동으로 unique 속성을 추가해 복합 인덱스를 생성한다.