[DB] B+Tree 란? 그리고 자바 구현

B+Tree

• 데이터베이스의 인덱스에 자주 사용된다.
• B-Tree 계열의 Balanced Tree 종류 중 하나이다.
• B+Tree는 데이터베이스 인덱스와 파일 시스템 사용에 더 적합할 수 있도록 만들어졌다.

구조

• 이름처럼 트리 구조 - 바이너리 트리랑 개념적으로는 비슷함
  • key 값으로 정렬되어 있다.
  • 자식 노드가 여러개다.
• 각각의 노드가 메모리가 아닌 디스크에 저장되어 있다.
• 데이터는 leaf노드에만 있다.

(각각의 노드가 메모리가 아닌 디스크에 저장되어 있다.)

 

 

디스크에서도 메모리에서처럼 포인터 개념을 사용할 수 있다.

각각의 노드에 sibling으로 가는 포인터가 존재한다.⇒ Range 쿼리하기에 좋다.

→ 예시: SELECT * FROM table WHERE age >= 30 AND age < 40 처럼 범위 조건 조회가 빈번하다.

B+ Tree 읽기

• key 3인 데이터 찾기
  • binary search를 통해 자식 노드 중 어디로 갈지 정한다.
  • key 3인 곳을 포인트를 따라 찾아갈 수 있다.
    • d3

B+ Tree 쓰기

• B+Tree에 새로운 키를 추가하는 게 약간 복잡하다.
  • 새로운 값을 넣으려면 binary search로 들어갈 자리를 쭉 포인터를 타고 찾아간다.
  • 자리를 찾으면 그 자리에 추가한다.
  • 만약 자리가 없다면, 새로운 노드를 추가한다. 기존 꽉 찬 노드의 절반을 새 노드에 옮긴다.
  • parent node의 정보를 새로 업데이트 해주고 새 노드에도 정보를 업데이트 해준다.
    • 대부분의 경우 3-4 뎁스정도면 모든 데이터를 처리할 수 있다
    • 실제로는 노드 하나에 자식이 몇 백개가 되기 때문에 depth가 많이 늘어나지 않는다
• B+Tree 쓰기는 여러 Disk write 이 필요할 때가 있다
• 중간에 오류가 발생하면 데이터가 손상될 수 있다
• 대부분 Write-ahead log(WAL) 라는 파일에 어떤 write을 할 지 미리 써 놓고 B+Tree 업데이트를 시작한다

B+Tree(RDB) vs LSM Tree(NoSQL)

• Read의 경우 B+Tree가 빠르다.
  • B+Tree는 트리를 따라서 내려가면 바로 읽을 수 있다.
  • 뎁스또한 3~4밖에 되지 않는다.
    • 최악의 경우에도 3~4번의 Read를 통해 찾을 수 있다.
• Write의 경우 LSM이 빠르다
  • LSM Tree는 memtable과 log-file 에만 쓰면 끝
  • B+Tree는 여러번의 Disk Write이 필요할 수 있다. + WAL에도 써야한다.
• 좋은 개발자라면 자신이 개발하고 있는 프로덕트가 어떤 Read/write 패턴을 가지고 있는지 생각해서 선택하는 것이 좋다.

구현 - 메모리 활용 방식

/**
 * 간단한 BTree (메모리 버전으로 구현)
 * 각 노드 최대 자식은 10개로 구현
 * 실제 DB와 달리 메모리 상에서만 유지
 */
public class BPlusTree {
    private static final int ORDER = 10;
    private Node root;

    public BPlusTree() {
        root = new LeafNode();
    }

    /**
     * 검색
     */
    public String search(int key) {
        return root.search(key);
    }

    /**
     * 삽입
     */
    public void insert(int key, String value) {
        root.insert(key, value);
    }

    abstract static class Node {
        // B+Tree에서 내부 노드는 검색용 키만, 리프 노드는 키-값 페어를 저장
        // 공통적으로 '검색'과 '삽입' 메서드를 갖는다.
        abstract String search(int key);
        abstract SplitResult insert(int key, String value);
    }

    // 내부 노드 구현
    static class InternalNode extends Node {
        List<Integer> keys = new ArrayList<>();
        List<Node> children = new ArrayList<>();

        @Override
        String search(int key) {
            int i = 0;
            while (i < keys.size() && key >= keys.get(i)) {
                i++;
            }
            return children.get(i).search(key);
        }

        @Override
        SplitResult insert(int key, String value) {
            int i = 0;
            while (i < keys.size() && key >= keys.get(i)) {
                i++;
            }

            SplitResult splitResult = children.get(i).insert(key, value);

            if (splitResult != null) {
                keys.add(i, splitResult.key);
                children.set(i, splitResult.left);
                children.add(i + 1, splitResult.right);

                if (keys.size() >= ORDER) {
                    return splitInternal();
                }
            }
            return null;
        }

        private SplitResult splitInternal() {
            // 절반으로 분할
            int mid = keys.size() / 2;
            int upKey = keys.get(mid);

            InternalNode rightNode = new InternalNode();

            for (int i = mid+1; i < keys.size(); i++) {
                rightNode.keys.add(keys.get(i));
            }
            for (int i = mid+1; i < children.size(); i++) {
                rightNode.children.add(children.get(i));
            }

            // this(왼쪽)에서 mid 이후 데이터 제거
            while (keys.size() > mid) {
                keys.remove(keys.size()-1);
            }
            while (children.size() > mid+1) {
                children.remove(children.size()-1);
            }

            // SplitResult 반환
            SplitResult split = new SplitResult();
            split.key = upKey;
            split.left = this;
            split.right = rightNode;
            return split;
        }
    }

    // 리프 노드 구현
    static class LeafNode extends Node {
        List<Integer> keys = new ArrayList<>();
        List<String> values = new ArrayList<>();

        @Override
        String search(int key) {
            for (int i = 0; i < keys.size(); i++) {
                if (keys.get(i) == key) {
                    return values.get(i);
                }
            }
            return null;
        }

        @Override
        SplitResult insert(int key, String value) {
            int i = 0;
            while (i < keys.size() && keys.get(i) < key) {
                i++;
            }
            // 동일 키 처리(학습용으로 단순 overwrite)
            if (i < keys.size() && keys.get(i) == key) {
                values.set(i, value);
                return null;
            } else {
                keys.add(i, key);
                values.add(i, value);
            }

            // 노드가 초과하면 split
            if (keys.size() >= ORDER) {
                return splitLeaf();
            }
            return null; // split 없음
        }

        private SplitResult splitLeaf() {
            int mid = keys.size() / 2;
            int upKey = keys.get(mid);

            LeafNode rightNode = new LeafNode();
            for (int i = mid; i < keys.size(); i++) {
                rightNode.keys.add(keys.get(i));
                rightNode.values.add(values.get(i));
            }

            // leftNode(this): mid 전까지 남기기
            while (keys.size() > mid) {
                keys.remove(keys.size()-1);
                values.remove(values.size()-1);
            }

            SplitResult split = new SplitResult();
            split.key = upKey; // 리프 split 시, 보통 리프의 첫 키를 올림
            split.left = this;
            split.right = rightNode;
            return split;
        }
    }

    static class SplitResult {
        int key;
        Node left;
        Node right;
    }
}

 

참고

https://www.youtube.com/watch?v=yLe7_3cGSeU&ab_channel=코맹탈출-실리콘밸리개발이야기