B Tree

이진 트리

• 하나의 부모가 하나의 자식
• 균형이 맞지 않으면 검색 효율 급락

⇒ 이진 트리 구조의 간결함, 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 기대할 수 있기에 개선하려고 함

B Tree

: 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종

이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것

• 자식 수에 대한 일반화 + 하나의 레벨에 더 저장됨 + 트리의 균형을 자동으로 맞춤 → 단순하고 효율적이며 레벨로만 따지면 완전히 균형을 맞춘 트리

  대량의 데이터를 처리해야 할 때, 한 노드에 많은 데이터를 가지는 것은 상당히 큰 장점이다.
  
  대량의 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD에 저장해야하기 때문!
  
  ex) 한 블럭이 1024 바이트면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용 발생. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다.
  
  → B-Tree는 이러한 장점을 토대로 데이터베이스 시스템의 인덱스 저장 방법으로 애용하고 있음

규칙

• 노드의 자료 수가 N, 자식 수는 N+1
  
• 각 노드의 자료는 정렬된 상태
  
• 루트 노드는 적어도 2개 이상의 자식
• 루트 노드를 제외한 모든 노드는 M/2개 ~ M개의 자료를 가짐
  
• 특정 노드의 왼쪽 서브 트리는 특정 노드의 값보다 작은 값들로, 오른쪽 서브 트리는 큰 값으로
  
• 외부 노드로 가는 경로의 길이는 모두 같음
• 모든 리프 노드는 같은 레벨에 존재
• 입력 자료는 중복 될 수 없음

탐색 과정

1. 루트부터 탐색 시작
2. 값을 찾으면 탐색 종료
3. 탐색 값과 key값을 비교해 알맞은 자식 노드로 내려감
4. 해당 과정을 리프 노드에 도달할 때까지 반복
5. 리프에서 탐색 값을 찾지 못하면 트리 내에 값이 없는 것

삽입 과정

1. 트리가 비었다면 루트 노드를 할당하고 값 삽입

2. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드 탐색

3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료

4. 리프 노드가 부적절한 상태면 분리

   적절한 상태 : 해당 노드의 데이터 개수가 허용 범위 안에 있는 것

• 분리가 일어나지 않는 경우
  • 데이터를 삽입할 리프 노드를 탐색하고, 해당 노드에 데이터 삽입
  • 해당 노드가 적절한 상태면 종료
• 분리가 일어나는 경우
  • 데이터를 삽입할 리프 노드를 탐색하고, 해당 노드에 데이터 삽입
    • 해당 노드의 왼쪽 값들은 왼쪽 자식으로, 오른쪽 값들은 오른쪽 자식으로 분리
    • 부모 노드에도 같은 분리 반복

삭제 과정

• 리프 노드에서 삭제
  • 리프 노드에서 삭제하더라도 최소 유지 개수를 만족하는 경우 → 노드 삭제
    
  • 최소 유지 개수를 만족 못하지만 형제 노드에서 값을 가져올 수 있는 경우
    • K를 Parent와 바꿈.
    • 왼쪽 형제 노드에게서 값을 빌려올 수 있다면 Lmax와 Parent를, 오른쪽 형제에게서 값을 빌려올 수 있다면 Rmin과 Parent를 바꿈. 둘 다 가능하면 하나를 선택하면 된다.
  • 최소 유지 개수를 만족 못하고, 형제 노드에서 값을 못 가져오고, 부모 노드를 분할
    • K 삭제
    • Parent를 부모 노드에서 분할하여 형제 노드에 합침 → 부모 노드의 값이 하나 줄고, 자식 노드의 수도 하나 줄어 최소 유지 개수 만족
      
  • 다 만족 못할 때 → 내부 노드에서 값을 삭제할 때, 현재 노드와 자식 노드 모두 key 개수가 최소인 경우 동일
    
• 내부 노드에서 삭제
  • 현재 노드 혹은 자식 노드의 최소 유지 개수보다 큰 경우
    • K의 Lmax 혹은 Rmin 과 바꿈
    • 이후는 리프 노드에서의 삭제와 동일
  • 현재 노드와 자식 노드 모두 최소인 경우 → 재구조화 필요
    • K삭제, K의 자식을 하나로 합침(N1)
    • K의 Parent를 K형제에 합침(N2)
    • N1을 N2의 자식이 되도록 연결
      • N2 값 수 > 최대 : key 삽입 과정으로 가 동일하게 분할
      • N2 값 수 < 최대 : 2번으로 가 동일 과정 반복