1부 스토리지 엔진 :: 2장 - B-트리 개요

• 불변성: 저장 구조의 설계와 구현 방식을 결정하는 중요한 속성
• 가변 자료 구조는 인플레이스 업데이트 방식을 사용한다.
  • 데이터 삽입 및 삭제, 업데이트 시 데이터 저장 위치에 새로운 데이터를 바로 쓰는 방식이다.

이진 탐색 트리

• Binary Search Tree는 정렬된 인메모리 자료 구조로, 키-값 쌍 검색에 사용된다.
• BST는 키와 두 개의 자식 포인터가 저장된 여러 노드로 구성된다.
• 탐색은 루트 노드에서 시작하고 트리에는 단 한 개의 루트 노드만 있을 수 있다.

트리 밸런싱

• 노드 삽입 작업에는 특정 패턴이 없으며, 삽입하는 값에 따라 트리가 불균형해질 수 있다.
  • 불균형 트리란 트리가 한쪽으로 길게 뻗은 최악의 상황을 나타낸다.
• 균형 트리란 노드 개수가 N일 때 높이가 log2N이고 두 서브트리의 높이 차이가 최대 1인 트리이다.
  • 불균형 트리는 이진 탐색 트리 성능을 극대화 할 수 ㅇ벗다.

디스크 기반 스토리지용 트리

• 불균형 트리의 최악의 시간 복잡도는 O(N)이다. 반면 균형 트리의 평균 시간 복잡도는 O(Log2N)이다.
• BST는 트리의 팬아웃(노드가 가질 수 있는 최대 자식 노드 갯수)이 낮기 때문에 트리 밸런싱과 노드 재배치, 포인터 갱신이 자주 발생한다.
• 디스크 저장에 적합한 트리 특성 두 가지
  • 인접한 키의 지역성을 높이기 위한 높은 팬아웃
    • 노드는 키 순서에 따라 삽입되지 않기 때문에 자식 포인터가 여러 다른 디스크 페이지를 가리킨다.
  • 트리 순회 중 디스크 탐색 횟수를 줄이기 위한 낮은 트리 높이
    • 이진 트리는 팬아웃이 2이기 때문에 높이는 전체 노드 수의 로그 값이다.
    • 따라서 특정 노드를 찾기 위해서는 O(Log2N)번의 탐색과 디스크 전송이 필요하다.

디스크 기반 자료 구조

하드 디스크 드라이브

• 전통적인 알고리즘 대다수는 디스크 드라이브가 영속적 저장 매체로 가장 널리 사용되던 시기에 개발됐기 때문에 알고리즘 설계에 이러한 영향을 크게 받았다.
• 디스크에서는 탐색 작업이 랜덤 읽기 비용의 많은 부분을 차지한다.
  • 디스크를 회전하고 읽기/쓰기용 헤드를 원하는 위치까지 물리적으로 옮겨야 하기 때문이다.
• 디스크 최소 전송 단위는 섹터이다. 섹터의 크기는 보통 512바이트에서 4Kb 사이이다.
• 물리적 헤드 이동은 HDD 작업 중 가장 비용이 높은 작업이다. 따라서 디스크에서 연속된 메모리 섹터를 읽거나 쓰는 순차적 I/O를 극대화해야한다.

솔리드 스테이트 드라이브

• SSD(Solid State Drive)는 물리적으로 움직이는 부품이 없다.
• 일반적으로 메모리 셀로 구성되어 있고, 셀을 연결하면 스트링의 배열이 페이지를 이룬다.
• 셀은 한 개 또는 여러 개의 비트를 저장한다.
• 페이지의 크기는 보통 2~16kb이고, 블록은 일반적으로 64 ~ 512개의 페이지로 구성된다.
• 페이지는 읽고 쓸 수 있는 가장 작은 단위이고, 비어 있는 메모리 셀에만 쓸 수 있다.
• 삭제할 수 있는 가장 작은 단위는 여러 페이지로 구성된 블록이다.
• 페이지 ID를 실제 위치와 맵핑하고 비어 있거나 쓰여진 혹은 삭제된 페이지를 관리하는 플래시 메모리 컨트롤러를 플래시 변환 레이어(FTL, Flash Translation Layer)라고 부른다.
• 일부 블록에는 이미 사용중인 페이지가 있을 수 있다.
• HDD와 SSD는 개별 바이트 단위가 아닌 메모리 청크 단위로 데이터를 참조한다.

디스크 기반 자료 구조

• 효율적인 디스크 기반 자료 구조가 설계가 어려운이유는 작업 단위가 블록이라는 제약 때문이다.
  • 블록 특정 위치 참조를 위해 블록 전체를 읽어야한다.
• 디스크 기반 자료구조는 저장 매체의 구조를 고려해서 설계해야 하며 디스크 접근 횟수를 최소화해야한다.
• 내부 구조를 최적화 하고 지역성을 높여 페이지를 넘나드는 포인터를 최소화해야한다.
• B-트리는 팬아웃을 크게 하고 높이와 노드 포인터 갯수, 밸런싱 빈도를 줄인 트리이다.

유비쿼터스 B-트리

• B-트리 원리는 도서관에서 캐비닛과 선반, 서랍을 순서대로 찾은 뒤에 서랍 안의 카드에서 원하는 도서를 찾는 과정과 유사하다.
• B-트리는 키의 순서가 보장되는 자료 구조이다.
• 노드 키를 기준으로 정렬해서 저장하기 때문에 이진 탐색과 같은 알고리즘을 사용해 특정 키를 찾을 수 있다.
• 따라서 B-트리 탐색의 시간 복잡도는 로그 시간이다.

B-트리 계층

• 각 노드는 최대 N개의 키와 N+1개의 자식 노드 포인터를 저장한다.
• 루트 노드
  • 트리의 최상위 노드로 부모 노드가 없음
• 내부 노드
  • 루트와 리프 노드를 연결하는 모든 노드. 트리에는 일반적으로 한 레벨 이상의 내부 노드가 있음
• 리프 노드
  • 자식 노드가 없는 트리의 최하위 계층 노드

B+트리

• B-트리는 루트와 내부, 리프 노드가 포함된 모든 레벨에 값을 저장할 수 있는 트리이다.
• B+트리는 리프 노드에만 값을 저장할 수 있다.
  • 내부 노드에는 피르 노드에 저장된 값을 찾기 위해 검색 알고리즘에 필요한 구분 키만 저장한다.
• b+트리는 리프 노드에 값을 저장하기 때문에 모든 작업은 리프 노드에만 영향을 미치며 상위 레벨의 노드는 노드 분할 혹은 병합이 일어날 때에만 영향을 받는다.

구분 키

• B-트리 노드에 저장된 키를 인덱스 엔트리, 구분 키, 또는 디바이더 셀이라고 부른다.
• 각 키는 트리를 해당 키 범위의 서브트리로 분할한다.
• 키는 정렬돼 있기 때문에 이진 검색에 사용할 수 있다.

B-트리 탐색의 시간 복잡도

• B-트리 탐색의 시간 복잡도는 블록 전송 횟수와 비교 횟수라는 두 가지 관점에서 계산할 수 있다.
• 전송 횟수 관점에서 복잡도의 로그 밑은 N이다.
  • 각 레벨에는 이전 레벨보다 K배 많은 노드가 있고 자식 포인터를 따라가면 탐색 공간이 N의 배율로 감소한다.
• 특정 키를 찾기 위해서 최대 logK M(M은 전체 노드 개쉬개의 페이지에 접근해야 한다.
  • 루트에서 리프까지 거쳐 가는 자식 포인터의 수는 트리의 최대 레벨 또는 높이와 같다.
• 비교 횟수 관점에서 보면 각 노드 안에서 이진 탐색을 사용해 키를 찾기 때문에 복잡도의 로 그 밑은 2다. 비교할 때마다 탐색 공간이 절반으로 줄어들기 때문에 복잡도는 log2M이다

B-트리 탐색 알고리즘

• 탐색의 목적은 특정 키 또는 바로 앞 키를 찾는 것이다.
  • 포인트 쿼리와 업데이트, 삭제 작업 시에는 정확히 일치하는 키를 찾아야 한다.
  • 범위 스캔과 새로운 노드 삽입 시에는 대상 키의 바로 앞의 값을 찾아야한다.
• 탐색 알고리즘은 루트 노드에서부터 이진 검색을 수행한다.
  • 인덱스 키는 인접한 두 개의 키 사이의 범위를 포함하는 서브 트리를 가리킨다.
  • 해당 서브트리를 찾고 리프 노드까지 포인터를 따라간다.
• 이 탐색 과정을 반복하면서 대상 키를 찾아 반환하거나 트리에 존재하지 않는 키인 경우 바로 앞의 값을 반환한다.

키 개수

• 키와 자식 오프셋 수를 계산하는 다양한 방식이 있다.
• 페이지에 k~2k개의 키가 있으며 최소 k+1에서 최대 2k+1개 자식 노드를 가리키는 포인터를 저장할 수 있다.
• 루트 페이지는 1~2k개의 키를 포함할 수 있으며 리프가 아닌 모든 페이지는 최대 I + 1개의 키를 포함한다.

B-트리 노드 분할

• B-트리에 새로운 노드를 삽입하려면 우선 대상 리프를 찾고 삽입할 위치를 결정해야한다.
• 리프 노드에 남은 공간이 없는 노드를 오버플로우 상태라고 표현한다.
• 오버 플로우 상태의 노드에 새로운 키를 삽입하려면 노드를 분할해야한다.
  • 리프 노드: 노드에 최대 N 개 키-값 쌍을 저장할 수 있고 새로운 키-값 쌍 삽입 시 용량이 초과되는 경우
  • 리프 아닌 노드: 노드에 최대 N+1개 포인터를 저장할 수 있고 포인터 추가 시 용량이 추가되는 경우
• 노드 분할은 새로운 노드를 할당해 키 절반을 새로운 노드로 옮기고 첫 번째 키와 포인터를 부모 노드에 추가하는 방식으로 이뤄진다.
  • 이러한 키를 승급했다고 표현한다.
  • 분할이 발생한 키를 분할 지점(미드 포인트)라고 부른다.
  • 이 키의 앞 키는 그대로 남겨 두고 나머지 키는 새로 생성한 형제 노드로 옮긴다.
• 부모 노드에 승급 키와 포인터를 추가할 공간이 없을 경우, 부모 노드도 분할해야한다.
  • 이런 경우 노드 분할이 루트 노드까지 재귀적으로 전파될 수 있다.
• 트리에 용량이 부족하면 루트 노드를 분할해야 한다. 분할 지점의 키를 포함하는 새로운 루트 노드를 생성한다.
  • 기존의 루트 노드와 생성된 형제 노드는 다음 레벨로 강등되고 트리의 높이가 한 레벨 증가한다.
  • 루트 노드 분할로 인해 새로운 루트 노드를 할당하거나 노드 병합으로 인해 새로운 루트 노드가 형성되면 트리의 높이가 변한다.
  • 반면 리프와 내부 노드 레벨에서는 트리가 수평으로만 확장한다.
• 리프 노드가 아닌 노드 분할은 항상 하위 레벨 노드의 분할로 인해 발생한다.
  • 그렇기 때문에 새로운 포인터가 항상 추가되고, 부모 노드에 남은 공간이 없다면 마찬가지로 분할해야 한다.
• 분할이 완료되면 두 노드 중 새로운 키를 삽입할 노드를 선택한다.
  • 승급된 키보다 작다면 분할 노드에 삽입하고 더 크다면 새로운 노드에 삽입한다.
• 분할 네 단계
  • 새로운 노드 할당
  • 분할 노드 키의 절반을 새로운 노드로 복사
  • 새로운 키를 알맞은 노드에 삽입
  • 분할 노드의 부모 노드에 분할 키와 새로운 노드를 가리키는 포인터 추가

B-트리 노드 병합

• 키를 삭제하는 경우에는 우선 대상 키가 포함된 리프 노드를 찾는다.
• 리프 노드를 찾았으면 해당 키와 값을 삭제한다.
• 키를 삭제하다보면 노드에 저장된 값이 너무 적은 경우가 생기는데, 이러한 때에는 형제 노드들을 병합해야 한다. 이를 언더플로우라고 한다.
• 리프노드: 노드에 최대 N개 키-값 쌍을 저장할 수 있고, 두 노드의 총 키-값 쌍의 수가 N보다 작거나 같은 경우
• 리프가 아닌 노드: 노드에 최대 N+1개 키-값 쌍을 저장할 수 있고, 두 노드의 총 키-값 쌍의 수가 N+1보다 작거나 같은 경우
• 분할 세 단계
  • 모든 키를 오른쪽 노드에서 왼쪽으로 복사한다.
  • 부모 노드에서 오른쪽 노드를 가리키는 포인터 제거한다.
  • 오른쪽 노드를 제거한다.