B-Tree

• 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종
• 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

1. 메모리 계층 구조

• 지금까지 다룬 자료구조 -> 메인메모리에 상주하는 데이터
• 보조기억장치에 데이터를 저장하는 DB와 파일시스템은 빅오 의미 없어짐
• 자료구조를 HW특성과 잘 맞물려 변형한다면 보조 기억 장치로 삽입, 탐색, 삭제 시 성능 향상 가능

• “DB에 접근하는 횟수를 줄여라”
  • 프로세스 시작 시 HDD에서 필요한 메모리 메인 메모리로 가져온 후 이 메모리 기반으로 프로그램 수행하기 때문
  • 따라서 대부분의 자료구조 메인 메모리를 기준으로 설계
  • DB는 최대한 효율적으로 데이터를 관리할 뿐 HDD가 갖는 HW적 한계를 뛰어넘는 것은 아님
• DB가 데이터를 삽입, 탐색, 삭제 하기 위한 자료구조
  • B 트리
  • B+ 트리

2. B 트리

• m-way 탐색 트리의 일종
  • m: 노드가 가질 수 있는 최대 자식 개수
  • BST
    • 2-way 탐색 트리
    • 자식은 둘이지만 노드가 가지는 키는 하나
  • m-1는 노드가 가질 수 있는 최대 키 개수

1) key

• 노드에 키가 하나일 때와 여러 개일 때 차이

• m이 커지면서 트리 높이가 줄어듬
  • 메모리 접근 횟수가 줄었다는 뜻
• 비교 연산 횟수는 늘어남
• 결국 성능은 비슷하지 않나?
  • 아님
  • 이 자료구조가 HDD에 저장되어 있기 때문
  • 메인메모리에서 데이터 가져올 때 40클럭 소요 / HDD에서 데이터 가져올 때 50만 클럭 소요

2) 결론

• HDD에 상주하는 자료구조 설계하려면 한 노드에 최대한 많은 키를 담아 메모리 접근 횟수를 줄여야 함
• 그렇다고 노드 크기 무작정 늘릴 시 한번에 한 노드를 가져올 수 없게 됨

3) m-way 탐색 트리

• 서브트리를 최대 m개 가진다.
• 한 노드에서 key는 정렬되어 있다.
• 어떤 키 K의 왼쪽 서브트리의 모든 키는 K보다 작다.
• 어떤 키 K의 오른쪽 서브트리의 모든 키는 K보다 크다.
• 서브트리도 m-way 탐색 트리이다.

• 2 <= 루트 노드의 서브트리 개수 <= m
• math.ceil(m/2) <= 루트를 제외한 노드의 서브 트리 개수 <= m
• math.ceil(m/2)-1 <= 루트를 제외한 노드의 키 개수 <= m-1
• 모든 리프노드는 같은 레벨에 있다.

3. 삽입, 삭제 연산

1) 삽입

• 아무 것도 없었을 때 최초 레코드 1 삽입
  • 첫 번째 레코드 삽입되면 키 1을 가진 루트노드가 만들어짐
  • 루트 노드 이자 리프 노드
• 두 번째 레코드 삽입
  • 키 2가 루트 노드에 추가

• split
  • 노드 끝에 3 삽입 시 최대 키 개수를 넘기 때문에 이를 분리시켜야 함
  • 가운데 키 2를 새로운 노드에 삽입하여 부모로 올림
  • 키 1이 있는 노드는 키 2가 있는 노드의 왼쪽 서브트리로 만듬
  • 키 3이 있는 노드는 키 2가 있는 노드의 오른쪽 서브트리로 만듬
  • 최종적으로 트리 높이 높아짐

• 부모 노드가 있는 경우 split
  • 키 5가 삽입되면 키 4 뒤에 키 5 추가 -> 최대 키 개수 넘김
  • 노드에서 가운데 키 값인 4가 부모노드로 올라가 키 2뒤에 삽입
  • 키 3은 키 4의 왼쪽 자식이되고 키 5는 키 4의 오른쪽 자식이 됨
  • 데이터 연속 추가 시 부모노드도 최대 키 개수 넘길 경우 부모 노드도 연쇄적 split 진행

2) 삭제

• B 트리에서 키 삭제는 향상 리프노드에서 진행
• 리프 노드가 아닌 노드에서 키 삭제해야 할 시 대체 키를 바꾼 후 삭제 진행

• 위의 노드에서 키 6을 삭제한다고 가정
  • 키 6이 있는 노드는 리프노드가 아니므로 대체 키를 찾아야함
  • 대체 키는 왼쪽 서브트리에서 가장 큰 키인 5가 됨 (더 큰 키 있으면 그 키가 대체 키가 됨)
  • 그 후 키 6 노드 삭제
  • 아래 그림처럼 된다.

• m=3 인 3-way 트리는 최소한 서브트리가 2개는 있어야 함
  • 서브트리 특성 깨짐
• donate (회전 연산)
  • 왼쪽이나 오른쪽 자식 노드에 노드의 최소 키 개수를 충족한 후 남는 키가 있는지 질의 (여기서는 키가 2개이상인 노드가 있는지)
  • 오른쪽 자식 노드의 키가 7과 8 두 개가 있어서 최소 키 개수 한 개를 빼도 한 개가 남는다 -> 빈 노드로 donate 가능
  • 노드의 가장 작은 키 7을 빈 노드로 바로 주면 트리 규칙 깨짐
    • 부모 노드의 키 5가 왼쪽 서브 트리로 가고 7이 부모 노드로 간다.
  • 아래 그림처럼 된다.

• 키 5 삭제 시
  • 키 7의 노드 서브 트리 1개 -> 서브 트리 특성 위반
  • donate 불가
• merge
  • 해당 노드의 오른쪽 (또는 왼쪽) 자식노드에 있는 키 값과 부모노드의 키 값을 모으는 작업
  • 공백이 된 노드는 제거
  • 트리구조 변경됨

• 키 7과 키 8을 가진 노드가 병합됨
  • 부모 노드가 빈 노드 - donate 불가능, 다시 merge
  • 부모 노드의 키 4가 키 2를 가진 노드의 마지막에 삽입

4. B+ 트리

• B트리의 변형으로 실제 데이터베이스는 B+트리로 구현된 경우가 많다.

• 노드는 인덱스 노드와 데이터 노드로 구성
  • 리프 노드는 다 데이터 노드. 즉, 리프노드에 모든 데이터들이 담겨있음
• 모든 리프노드가 이중연결리스트 형태를 띄고 있음
  • B트리는 옆에 있는 리프노드 검사할때 다시 루트노드부터 검사
  • B+ 트리는 리프노드에서 선형검사 수행 가능
• 인덱스 노드의 키들이 데이터 노드에서 중복해서 나타남
  • 해당 키의 오른쪽 서브트리에서 가장 작은 키가 있어야 할 곳에 해당 키가 중복되어 나타남
  • 인덱스 노드끼리는 중복 X

5. index

https://velog.io/@syleemk/%EB%A9%B4%EC%A0%91-%EB%8C%80%EB%B9%84-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EC%9D%B8%EB%8D%B1%EC%8A%A4