B+ tree Index

B+ tree

B+-Tree Index Files

• 트리 구조는 검색에 유용하다 왜냐하면 조건에 맞는 노드를 찾아갈 때 필요없는 것을 순식간에 자를 수 있기 때문이다.(잘라내기=pruning 이라고 한다) 이 때문에 구글, 네이버 등 검색 사이트들에서는 이러한 트리의 색인을 이용해 검색 알고리즘에 사용한다.
• 트리니까 당연히 루트가 있다. rooted tree
  • b-tree는 balanced 트리로 다양한 변형이 존재한다. 그 중 b+ tree가 구조상 삽입,삭제가 쉽기 때문에 가장 많이 사용한다.

    • balanced 트리는 루트에서 leaves 노드들 까지의 깊이(길이)가 같은 트리를 말한다. balanced 트리가 성능이 가장 좋다.

      • unbalanced 트리같은 경우, 한쪽으로 치우쳐 있을 경우에는 검색 성능이 굉장히 나빠진다. 데이터가 어디에 위치하느냐에 따라 검색 속도가 극단적으로 차이가 나게 된다.

    • 구글, 네이버와 같이 데이터도 굉장히 많고 동시 엑세스 사용자도 굉장히 많다. 따라서 balanced 트리가 되어야 검색하는 노드의 갯수가 줄어들기 때문에 성능이 좋아진다.

    • B+트리의 노드는 n개의 포인터와 n - 1개의 키값을 가질 수 있다.

      

      • $P_i$ : 포인터 (child node 또는 record를 가리키는 포인터)
      • $K_i$ : 키 값 (search-key value)
      • $P$와 $K$는 쌍으로 움직이고 $P_n$이 마지막에 홀로 남아있는 형태이다.
      • 따라서 포인터의 갯수가 키 값인 $K$보다 하나 더 많다.
      • 키 값은 알파벳 순으로, 사전 순으로, 또는 숫자가 작은 순으로 정렬되어 들어가있다.
        • $K_1$ < $K_2$ < $K_3$ < . . . < $K_{n–1}$
      • 이 때 이 n은 fanout 또는 blocking factor라고 부른다. 그리고 이 fanout값 n은 특정한 트리에서 고정되어있다.
        • 예를 들어 $P$는 포인터니까 $P$를 표현하는데 4byte를 쓴다고 가정
        • 키값은 10byte라고 가정
        • 위 두 개는 쌍으로 움직이므로 두 개를 합하면 14byte
        • 한 노드 사이즈를 1KB라고 가정. 즉 1024byte
        • 그러면 위 쌍은 1KB에 73개가 들어간다. 즉 $n-1$이 73이 되고 마지막에 포인터가 하나 더 들어가게 되므로 $n$은 74가 된다.
        • 즉 노드 하나를 어느 정도 크기로 가져갈지, 또한 포인터와 키 값을 어느정도 크기로 가져갈지에 따라 fanout이 고정되게 된다.

    • 루트가 아닌 nonleaf 노드는 $⎡n/2⎤$ ~ $n$개의 children을 갖는다.

      • 자료구조를 배울 때 많이 나오는 binary 트리는 최대 자식노드가 2개이기 때문에 트리의 깊이가 깊고 몸체가 얇다.
      • 메모리하고 하드디스크는 속도 차이가 1000배정도 나기 때문에 메모리에서는 일반적인 binary 트리와 같이 세로로 길어도 상관이 없지만 하드디스크는 속도가 느리니까 가능하면 노드의 크기를 크게 가져가고 깊이를 좁게 하고자 한다. 즉 가능하면 하나의 노드에 많이 집어넣으려고 한다.
      • 따라서 b+tree는 자식노드가 100개 이상으로 굉장히 많아 트리의 깊이는 얕고 몸체가 두꺼운 형태를 갖는다. 즉 절반 이상이 차도록 만든다.

    • 마찬가지로 leaf 노드 역시 $⎡(n–1)/2⎤$ ~ $n–1$ 개 사이의 값을 갖는다.

      • 트리들은 노드들간 포인터로 연결되는데, binary 트리는 memory용 자료구조로 memory는 접근시간이 빠르기 때문에 깊이가 깊더라도 빠르게 검색을 할 수 있다. 데이터베이스에서 자주 사용하는 b+트리는 보조기억장치 혹은 많은 사용자가 공유하기 때문에 자료 접근에 상대적으로 많은 시간이 걸린다. 그래서 트리의 깊이를 얕게 한 것이다.

    • 스페셜 케이스

      • 데이터 사이즈가 작을 떄는 루트가 위의 조건을 만족시키지 못할 수도 있다.
      • 만약 root가 leaf가 아니면 최소한 2개의 children을 갖는다.
      • 만약 root가 leaf이면(트리에 다른 노드가 없는 경우. 노드가 하나밖에 없는 경우) root는 $0$ ~ $(n–1)$개 사이의 values를 갖는다.

  • leaf node의 특징

    

    • leaf 노드 키 값 옆에 있는 포인터는 해당 키 값을 갖는 데이터가 하드디스크에 어디에 있는지를 가리키고 있다.
    • 특정 키 값이 여러개 있는 경우는 해당 키 값 아래에 붙게 되고(동명이인 같은 경우) 포인터는 가장 위를 가리킨다.
    • 키 값이 작은 것이 앞에 나온다. 즉 사전 순으로 정렬을 했을 때 키 값이 작은 것이 앞에 나온다.
      • $L_i$와 $L_j$가 있고 $i < j$라면 $L_i$의 serach key가 $L_j$의 search key보다 앞에 나온다.
    • 맨 마지막 포인터 $P_n$은 옆에 있는 노드를 가리킨다.

  • Nonleaf Node

    • leaf node와 전반적으로 똑같지만 차이점이 있다면
    • 포인터가 실제 데이터 레코드를 가리키고 있는 것이 아니라 child 노드를 가리키고 있다.
    • 그리고 $P_1$은 $K_1$보다 작은 키 값을 갖는 노드를 가리키고 있다.
    • $P_2$는 $K_1$보다 같거나 크면서 $K_2$보다 작은 노드를 가리키고 있다.
    • 즉 포인터는 키 값이 자기 앞에 있는것보다 같거나 크고 자기 뒤에 있는 것보다 작은 노드를 가리키게 된다.

Queries on B+ Trees

• Search (탐색)

  

  • Mianus를 찾고 싶다.
  • Mianus의 키 값이 있는 leaf 노드로 가서 거기에 있는 포인터를 따라가면 그 데이터가 있다.
  • 일단 루트로 들어간다. 루트로 가서 search key값이 찾고자 하는 값보다 큰 것 중에서 가장 작은 값을 갖는 키(Perryrridge)를 찾는다.
  • 그런 것(value $K_i$)이 존재하면 해당 노드를 가리키는 포인터($P_i$)를 따라간다. 그렇지 않으면 제일 오른쪽($P_m$, 여기서 m은 node에 있는 포인터들의 수)으로 내려간다.
  • 내려와서 찾고자 하는 키 값보다 큰 키 값들 중에서 가장 작은 값을 찾는다. 그런데 Mianus보다 큰 키 값이 없다. 이렇게 없으면 제일 오른쪽으로 내려간다.
  • 이렇게 따라 와보니까 leaf 노드다. leaf 노드에 왔으면 내가 찾고자 하는 키 값을 찾는다. Mianus가 있으므로 왼쪽 포인터를 따라 내려간다.
  • 그러면 내가 찾고자 하는 Mianus가 거기에 들어있다.
  • 만약 leaf까지 왔는데 내가 찾고자 하는 키 값이 없으면 내가 찾고자 하는 것이 없는 것.
• B+트리 쿼리의 특성
  • 쿼리를 처리할 때, 루트로부터 leaf 노드까지 인덱스 트리의 하나의 path를 탐색해 나간다. 즉 한 줄로만 내려간다는 것. 여러 줄로 내려가는 경우는 없다.
  • 만약 파일에 search key값이 K개가 있다면 검색 path의 길이는 $⎡log_{⎡n/2⎤}(K)⎤$보다 길지 않다.
    • 네이버나 구글을 생각하면 search key값의 갯수은 K는 엄청나게 크다.
    • n은 fanout. $n/2$는 최소 한도로 차 있는 데이터의 갯수. 많이 차 있어야지 트리가 짧아지니까 빨리 찾을 수 있다.
  • 예를 들어 search key values의 수가 100만이고 fanout인 n이 100일때, 검색 횟수는 최대 $log_{50}(1,000,000) = 4$밖에 안된다. 굉장히 빨리 찾을 수 있다.
• Update (삽입, 삭제, 갱신)
  • 어려운점
    • 갱신은 탐색하고 똑같지만 삽입 삭제는 node overflow가 생길 때 node split을 해야하므로 어렵다.
    • node underflow도 있다. 데이터 삭제에서 발생. 절반 이하로 떨어지게 되면 underflow가 생긴 노드를 합쳐야한다.
    • 밸런스를 항상 유지해야 하기 때문에 또 어려움이 발생
  • Insertion (삽입)

    • 일단 내가 들어갈 자리(leaf node)를 찾아야 한다.

    • 해당 leaf node의 search key값이 있으면

      • 그 뒤에 붙이면 된다.
    • 하지만 없으면
      • leaf node에 공간이 있으면 (key-value, ponter)의 쌍을 leaf node에 넣고 해당 포인터 아래에 데이터를 넣는다.
      • leaf node에 공간이 없으면 overflow가 발생. 기존의 데이터와 새로운 키값을 가지고 노드를 분할해야 한다. 그 다음에 새로운 데이터를 넣는다.
      • 분할의 경우는 처음 $⎡n/2⎤$개를 원래의 노드에, 그리고 나머지를 새로운 노드에 넣고 parent node를 생성한다!

    • 삽입 Example 1

      • 5, 8, 2, 10, 7, 1, 20, 21, 15, 4, 16 의 데이터를 삽입한다고 가정해보자

      • 이때 한 노드에는 3개의 키 값이 들어갈 수 있는 n = 4라고 가정

        

        1. 5, 8, 2를 삽입한다. 당연히 정렬되어 들어간다.

           

        2. 10을 집어넣으면 overflow가 발생한다. $⎡3/2⎤ = 2$개의 노드를 원래의 노드에, 나머지는 새로운 노드에 삽입하고 8을 parent node로 올린다.

           

        3. 7을 집어넣는다.

           

        4. 1을 집어넣으면 overflow가 발생한다. 마찬가지로 2개의 노드를 원래의 노드에 남기고, 나머지는 새로운 노드에 삽입하고 5를 parent node로 올린다.

           

        5. 20을 집어넣는다.

           

        6. 21을 집어넣으면 overflow가 발생한다. 마찬가지로 2개의 노드를 원래의 노드에 남기고, 나머지는 새로운 노드에 삽입한다. 20은 parent node로 올린다.

           

        7. 15를 집어넣는다.

           

        8. 4를 집어넣는다.

           

        9. 16을 집어넣으면 overflow가 발생한다. 부모 노드에도 overflow가 발생하므로 노드 분할을 진행해준다. 최종적으로 위와 같은 트리 형태를 띄게된다.

    • 삽입 Example 2

      

      • 위와 같은 트리는 색인구조. 마지막 leaf 노드의 포인터가 가리키는 버킷은 실제 데이터 파일들.

  • Deletion

    • Deletion에서는 underflow가 발생.

    • 데이터를 삭제할 시 데이터의 양이 절반 이하로 떨어지게 되면 인접한 노드하고 합치는 과정이 필요

    • 삭제 Example 1

      

    • 삭제 Example 2

      

    • 삭제 Example 3