B-Tree와 B+Tree

Tree 구조

• Tree구조는 데이터를 계층적으로 표현하는 자료구조이다.

• 기준에 따라 계층적으로 분류되어있기 때문에 삽입/삭제 수행시 O(logN)시간이 소요된다.

  • 일반적인 Array나 연결리스트 이용해 O(N)이 걸린다.

데이터베이스는 인덱스를 통해 데이터를 분류하고, 삽입/삭제/조회가 많이 일어나는 만큼 Tree구조로 데이터를 관리하기 적합하다.

따라서 데이터베이스는 Tree구조를 적용하는데, 그 중 B-Tree와 B+Tree를 적용하고 있다.

B-Tree

B-Tree는 이진 트리와 다르게 하나의 노드에 많은 정보를 가지고 있는 형태입니다.

그림의 파란부분은 각 노드의 key를 나타내며, 빨간부분은 자식 노드를 가르키는 포인터입니다.

특징

• 하나의 노드가 두개 이상의 값을 가질수 있음

  • 최대 자식 수의 개수에 따라 1, 2, 3, .. M차 B-tree가 있음

• 데이터가 정렬된 상태로 유지되어 있음(핵심)

  • key 값을 이용해 찾고하는 데이터를 트리 구조를 이용해 찾음

• 균형트리이기 때문에 B-tree는 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다는 균일성 장점을 가짐

균형 트리
- 균형 트리(Balanced-Tree)는 루트 노드부터 리프 노드까지의 거리가 일정한 트리 구조
  - 탐색 성능을 높이기 위해 균형 있게 높이를 유지
- 균형을 유지할 경우, 어떤 데이터를 검색할 때 빠른 속도로 데이터를 찾을 수 있음
- 일반적인 트리인 경우, 탐색하는데 평균적으로 O(logN) 시간 복잡도를 가지지만, 트리가 편향되어 있으면 최악의 시간 복잡도로 O(N)을 가짐
  - 이러한 단점을 보완하기 위해 트리가 편향되지 않도록 항상 밸런스를 유지하는 트리가 필요(균형 트리)
  - 자식들의 밸런스를 잘 유지하면 최악의 경우에도 O(logN) 시간 복잡도를 가짐
- ex) RedBlack-Tree(RBT), B-Tree

B-Tree의 연산

링크 첨부

B+Tree

B+Tree는 B-Tree에서 개선된 구조로, B-tree와 달리 실제 데이터는 리프노드에만 저장한다.

리프노드들간의 연결되어 있어, 범위 탐색시 B-Tree보다 좋은 성능을 낼 수 있다.

B+Tree 특징

• 중복 키를 가짐

  • 내부 노드들이 데이터를 가지고 있지 않기 때문에 리프 노드들이 키와 데이터를 모두 가지고 있어야 함

• 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메인 메모리를 더 확보해 더 많은 key를 수용할 수 있음

  • 하나의 노드에 더 많은 key들을 담을 수 있기 때문에 트리의 높이는 더 낮아짐

  • cache hit를 높일 수 있음

B-tree와 B+tree의 비교

비교	B-tree	B+tree
데이터 저장	모든 내부, 리프 노드들이 데이터를 가짐	리프노드만 데이터를 가짐
검색 속도	모든 노드 검색, 느림	리프노드에서 선형 탐색
키 중복	없음	있음
삭제	내부 노드의 삭제는 복잡하고 트리 변경이 많음	어떠한 노드든 리프에 있기 때문에 삭제가 쉬움
링크드 리스트	존재 x	리프 노드는 링크드 리스트로 저장됨
높이	특정 갯수의 노드는 높이가 높음	같은 노드일 때 B-tree보다 높이가 낮음
사용	데이터베이스, 검색엔진	멀티레벨 인덱스, DB 인덱스

DB는 여러 자료구조 중에 왜 B-Tree/B+Tree를 사용할까?

자료구조

• 해시테이블

  • 탐색 시간이 제일 빠름

  • 모든 값이 정렬되어 있지 않기 때문에, 해시 테이블에서는 특정 기준보다 크거나 작은 값(부등호)을 찾을 수 없음

  • 따라서 기준 값보다 크거나 작은 요소들을 항상 탐색할 수 있어야 하는 DB 인넥스 용도로는 맞지 않음

• RedBlack-Tree(RBT)

  • B-tree와 큰 차이는 하나의 노드가 가지는 데이터의 개수

  • RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터 요소만 가지고, B-Tree는 하나의 노드에 여러 개의 데이터 요소를 저장(배열처럼 저장되어 있음)함

    • B-Tree는 같은 노드 상 데이터를 탐색할 때는 포인터 접근이 아닌, 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 함

    • 하지만 RedBlack-Tree는 각 노드마다 무조건 하나의 데이터만 가지기 때문에 데이터를 접근할 때 무조건 참조 포인터로 접근하게 됨

• 배열

  • 참조 포인터라는 개념이 없고, 모든 데이터가 메모리 상 차례대로 저장되어 있어 접근이 매우 빠름

  • 탐색 속도로만 본다면 B-Tree보다 훨씬 빠름

  • 해시 테이블과 다르게 정렬 상태로 유지할 수있어 부등호 연산에도 문제가 없음

  • 하지만 배열이 B-Tree보다 빠른 것은 탐색뿐임

    • 배열 내에서 데이터의 저장, 삭제가 일어나는 순간 훨씬 비효율적인 성능이 발생하게 됨

B-Tree의 배열 형식의 접근과 RedBlack-Tree의 참조 포인터 접근

• 둘다 시간 복잡도는 O(logN)이지만, 이는 알고리즘 처리에 대한 이론적인 시간 계산 방식일 뿐임

  • 물리적, 절대적인 시간 개념으로는 배열 접근이 훨씬 빠름

• 참조 포인터로 접근

  • 참조 포인터로 메모리에 접근하는 것은 실제 메모리상 순서대로 저장이 되었든 안되었든, 접근하려는 주소를 연산을 통해 직접 알아내어야 함

  • 이는 주소를 알아내는데 CPU가 내부적으로 많은 연산을 하게 됨

• 배열 형식의 접근

  • 배열은 데이터들이 메모리 공간에 차례대로 저장되어 있으므로 접근할 주소를 바로 알 수 있음

  • 따라서 메모리 주소를 알아내는데 성능 영향이 없음

  • B-tree도 자식 노드를 접근할 때는 참조 포인터로 접근함

    • 하지만 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수는 확연히 줄어들고, 트리 내에서 데이터가 많아질수록 이러한 차이는 더욱 커짐

• 결국 포인터 접근 수의 차이로 B-Tree가 RedBlack-Tree보다 탐색 시간이 더 빠름

데이터베이스 인덱스로 적합한 자료구조인 B-tree

• 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없음

• 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능함

• 데이터 탐색뿐만 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가짐

InnoDB의 B+tree

• MySQL의 DB engine인 InnoDB는 B+tree로 인덱싱을 처리함

• InnoDB에서 사용된 B+tree

  • 같은 레벨의 노드끼리는 Linked List가 아닌 Double Linked List를 사용

  • 자식 노드로는 Single Linked List로 연결되어 있음

  • key의 범위마다 찾아가야할 페이지 넘버(포인터)가 있는데, 해당 페이지 넘버를 통해 곧바로 다음 노드로 넘어감

  • 리프 노드에서 디스크에 존재하는 데이터의 주소값을 구할 수 있고, Linked List 통해 탐색도 가능함