B Tree

 

개요

 B-Tree는 데이터베이스나 파일 시스템에서 주로 사용되는 자료구조이다. 디스크 액세스하는 수를 줄이기 위해 나온 자료구조이다. 대부분의 트리연산들은 O(h) (h는 트리의 높이)인데 B-트리는 노드에 가능한 최대로 값을 넣어서 높이의 수를 줄인다. 

 

 

특성

 루트를 제외한 모든 노드는 적어도 k-1개의 키를 포함해야한다. 최대로 2t-1의 키를 가질 수 있다. 

각 노드는 일련의 키와 여러 개의 자식 (자식 노드)을 가질 수 있다. 여기서 자식의 수는 0 또는 해당 키의 총 수에 1을 더한 값이 될 수 있다. 노드 [x]를 생각해보자. node [x]가 잎 노드 인 경우는 자식을 가지지 다 이것이 내부 노드인 경우 전체 자식 수는 n [x] + 1이다. 여기서 n [x]는 해당 키의 총 수이다.

 

제약 조건  # 1 : 루트 노드가 아닌 다른 노드는 적어도 (t - 1) 개의 키를 가져야한다.

제약 조건 # 2 : 루트 노드를 포함하는 모든 노드는 많아야 (2t - 1) 키를 가져야한다. 

제약 조건 3 : 모든 내부 노드 (루트 노드 제외)는 최소한 t 개의 자식을 가져야한다.

제약 조건 # 4 : 노드의 키는 오름차순으로 저장해야한다.

제약 조건 # 5 : 키의 왼쪽에있는 자식 노드의 모든 키는 그 키보다 작아야한다.  

제약 조건 # 6 : 키의 오른쪽에있는 자식 노드의 모든 키는 해당 키보다 커야한다.

 

삽입

 새 키는 항상 리프 노드에 삽입된다. 삽입 될 키를 k 라할때 BST와 마찬가지로 루트에서 시작하여 리프 노드에 도달 할 때까지 아래로 이동한다. 리프 노드에 도달하면 해당 리프 노드에 키를 삽입한다. 다만 키의 공간에 대해 미리 정의 된 범위가 있다. 따라서 노드에 키를 삽입하기 전에 노드에 추가 공간이 있는지 확인해야한다. 노드의 자식을 분할해서 공간을 확인한다. 분할 작업은 키를 위로 이동시킨다.

 

 

public void insert(int k)
    {
        Node r = root;
        if (r.numberOfNodes == 3) {
            Node s = new Node();
            root = s;
            s.numberOfNodes = 0;
            s.isLeaf = false;
            s.children[0] = r;
            splitChild(s, 1, r);
            insertNonfull(s, k);
        }
        else {
            insertNonfull(r, k);
        }
    }

    public void insertNonfull(Node node, int value) {
        int i = node.numberOfNodes;
        if (node.isLeaf) {
            while (i >= 1 && value < node.key[i - 1]) {
                node.key[i] = node.key[i - 1];
                i--;
            }
            node.key[i] = value;
            node.numberOfNodes++;
        }  else {
            while (i >= 1 && value < node.key[i - 1]) {
                i--;
            }
            i++;
            if (node.children[i - 1].numberOfNodes == 3) {
                splitChild(node, i, node.children[i - 1]);
                if (value > node.key[i - 1]) {
                    i++;
                }
            }
            insertNonfull(node.children[i - 1], value);
        }
    }
    public void splitChild(Node parentNode, int childIndex, Node newChild) {
        Node z = new Node();
        z.isLeaf = newChild.isLeaf;
        z.numberOfNodes = 1; 
        z.key[0] = newChild.key[2];

        if (!newChild.isLeaf) {
            z.children[1] = newChild.children[3];
            z.children[0] = newChild.children[2];
        }
        newChild.numberOfNodes = 1; 
        for (int j = parentNode.numberOfNodes + 1; j >= childIndex + 1; j--) {
            parentNode.children[j] = parentNode.children[j - 1];
            parentNode.key[j - 1] = parentNode.key[j - 2];
        }
        parentNode.children[childIndex] = z;
        parentNode.key[childIndex - 1] = newChild.key[1];
        parentNode.numberOfNodes++;
    }

 

 

삭제

1. 키 k가 노드 x에 있고 x가 리프 인 경우 x에서 키 k를 삭제한다. 

2. 키 k가 노드 x에 있고 x가 내부 노드인 경우
    a) 노드 x에서 k에 선행하는 자식 y가 t 키 이상인 경우, y를 루트로하는 서브 트리에서 k의 선행 k0를 찾는다. 재귀적으로 k0을 삭제하고 x를 k0로 바꾼다.
    b) y가 t 개의 키보다 적다면, 대칭적으로, 노드 x에서 k 다음에 오는 자식 z를 검사한다. z가 적어도 t 개의 키를 가지고 있다면, z를 근간으로하는 서브 트리에서 k의 후속 키 k0를 찾는다. 재귀적으로 k0을 삭제하고 x를 k0로 바꿉니다.
     c) y와 z 모두 t-1 키만있는 경우, k와 z를 모두 y와 병합하면 x와 k의 포인터가 모두 손실되고 y에는 2t-1 키가 포함된다. 그런 다음 z를 제거하고 y에서 k를 반복적으로 삭제한다.

3. 키 k가 내부 노드 x에 없다면 k가 트리에있는 경우 k를 포함해야하는 해당 하위 트리의 루트 x.c (i)를 결정한다. x.c (i)에 t-1 키만있는 경우 적어도 t 키가 포함 된 노드로 내려 가기 위해 필요한 경우 3a 또는 3b 단계를 실행한다. 그런 다음 x의 해당 하위 항목을 재귀적으로 반복한다.

    a) xc (i)가 t-1 개의 키만 가지고 있지만 적어도 t 개의 키가있는 직접적인 형제가있는 경우 xc (x)에서 키를 xc (i)로 이동하여 xc (i)는 x 또는 x에 바로 연결되는 형제이며, 해당 자식 포인터를 형제에서 xc (i)로 이동시킨다.
    b) xc (i)와 xc (i)의 쌍방의 형제가 t-1 키를 가지고 있다면 xc (i)를 하나의 형제와 병합한다.

 

 

 public boolean delete(int k) {
        Node x = root;
        return delete(x, k);
    }

    public boolean delete(Node node, int value) {
        int i = 1;
        while (i <= node.numberOfNodes && value > node.key[i - 1]) {
            i++;
        }
        if (node.isLeaf) {
            if (i <= node.numberOfNodes && value == node.key[i - 1]) {
                node.key[i - 1] = 0;
                for(int j = i - 1; j < node.numberOfNodes - 1; j++){
                    node.key[j] = node.key[j+1];
                    if(j+1 == node.numberOfNodes - 1)
                        node.numberOfNodes--;                    
                }
                return true;
            }
        } else {
            return delete(node.children[i - 1], value);
        }
        return false;
    }