bTree

B tree (B Tree)

bst(이진탐색트리)와 유사하지만
자식 의 노드가 2개보다 많은 트리
key값의 응용

부모 노드에 key 값을 1개 이상 저장하여,
(이 때, 이런 key는 오름차순 정렬된다)
자식 노드의 데이터 값을 비교하여,
노드의 위치를 배정한다

자식의 노드를 원하는대로 설정할 수 있기에
BST를 ‘일반화’한 tree 라고도 보기도 한다

b tree의 파라미터

1. 각 노드의 최대 자녀 노드 수 : M
   최대 M개의 자녀를 가질 수 있는 B tree를
   M차 B tree라고 부른다
2. 각 노드의 최대 key 수 : M-1
   (ex : 3차 B tree라면 key의 수는 최대 2개)
3. 각 노드의 최소 자녀 노드 수 : ceil(M/2) (올림)
   (ex : 3차 B tree의 최소 자녀 노드 수는 1.5의 올림)
   => 다만 이 조건은 root와 leaf 는 제외된다
   
4. 각 노드의 최소 key 수 : ceil(M/2) - 1
   => 각 파라미터에 따라서 기준이 달라지기도 한다

b tree의 특징

• 부모 노드의 key 수가 x개라면
  자녀 노드의 수는 언제나 x+1개다

• 각 노드는 최소 하나의 key는 가지기에
  몇 차 B tree인지 상관없이
  부모 노드는 최소 2개의 자녀를 가진다

  (M이 정해지면 root 노드를 제외하고
  각 부모 노드는 최소 ceil(M/2)개의 자녀 노드를 가질 수 있음)

• 모든 leaf 노드는 같은 level에 있다

b Tree의 삽입

• 추가는 항상 leaf 노드에 한다
  이 조건으로 처음에는 root에 하지만
  트리가 늘어날수록 find 한 후, 해당 위치의 leaf에 넣어줌

• 노드가 넘치는 경우, ‘가운데 key’를 기준으로
  좌우 key들은 분할하고, 가운데 key는 승진한다
  => 승진 :
  부모 노드가 없다면, 새로운 부모 노드가 생기고,
  그렇지 않다면 중간값이 부모 key값으로 올라온다
  (이 때, key가 또 넘치면 분리한다)

• key는 오름차순으로 정렬된다

b Tree의 삭제

• 삭제도 항상 leaf 노드에서 발생
  

• 데이터 삭제 후, 최소 key수보다 적어졌다면
  재조정을 한다
  (각 노드의 최소 키 수 : ceil(M/2) - 1)
  (root 노드 제외)
  

• 재조정 과정
  

  1. key의 수가 여유있는 형제의 지원을 받는다
     왼쪽 노드부터 지원받고, 그렇지 않으면 오른쪽 노드에서 받음
     왼쪽 노드에서 받는 경우
     왼쪽 노드의 가장 큰 key를 부모 노드의
     현재 노드와 왼쪽 노드 사이에 넣은 뒤
     원래 있었던 키를 현재 노드의 가장 왼쪽에 둔다
     

     오른쪽 노드에서 받는 경우는
     오른쪽 노드의 가장 작은 key를 부모 노드의
     현재 노드와 오른쪽 노드 사이에 넣은 뒤
     원래 있었던 키를 현재 노드의 가장 오른쪽에 둔다

  2. 1번이 안되는 경우, 부모의 지원을 받고 형제와 합침
     왼쪽 노드 존재 시,
     현재 노드와 왼쪽 노드 사이의 key를
     부모로부터 받고, 그 key와 현재 노드의 key를
     왼쪽 노드와 합치며,
     현재 노드를 삭제한다
     

     왼쪽 노드가 없을 시,
     오른쪽 노드와 현재 노드 사이의 key를
     부모로부터 받고,
     그 key와 오른쪽 key를 현재 노드에 합친다
     이후 오른쪽 노드를 삭제한다
     

  3. 2번 후, 부모에 문제가 있다면 부모를 기준으로 다시 재조정
     부모 노드가 root가 아니였다면,
     해당 위치부터 1번 프로세스로 진행
     

  부모 노드가 root노드이고 비어있다면
  부모 노드를 삭제하고,
  직전에 합친 노드를 root노드로 만든다
  

기본적인 탐색은 bst와 유사하게
해당하는 key과의 관계로 판단이 가능하다

• 부모 노드 데이터를 삭제해야 하는 경우
  이 경우, leaf 노드에 있는 데이터와 위치를 바꾼 후,
  리프를 삭제해야 한다
  (leaf 노드에 있는 데이터 중 어떤 데이터와 위치를 바꾸는가?)
  (predecessor 혹은 Succesor 찾기)
  (각각 선임자, 후임자)
  predecessor : 나보다 작은 데이터들 중 가장 큰 데이터
  (왼쪽 서브트리에서 가장 오른쪽의 후손)
  succesor : 나보다 큰 데이터들 중 가장 작은 데이터
  (오른쪽 서브트리에서 가장 왼쪽의 후손)

B tree의 시간 복잡도

평균, 최악의 경우
조회, 삽입, 삭제 모두 O(log n)

AVL, RB-Tree와도 동일하다
(이들도 모두 평균,최악 에 조회, 삽입, 삭제에 O(Log n))

그런데 왜 B Tree를 사용하지?

B tree의 용도

Database 는 기본적으로는
Secondary storage 에 저장된다
(SSD, HDD)

• Secondary Storage
  

  속도가 느린편, 용량은 많음
  데이터를 읽거나 쓸 때, block 단위로 이용
  (block : file system이 사용하는 논리적 단위
  보통 2의 승수로 표현됨 ex : 4,8,16 kb)
  (한번에 가져오기에 cache와 연관있음)
  

DB의 데이터는 사라지면 안되기에!
또한 DB의 사이즈는 작지 않기에 Secondary Storage에 저장

DB에서 데이터를 조회할 때,
최대한 적게 접근하는 것이 성능 면에서 좋음
(결국, HDD나 SDD는 Ram보다 느리기에, 자주 접근하면
성능적으로 좋지 않음)

Block 단위로 읽고 쓰기에,
연관된 데이터를 모아서 저장하면 효율적으로 읽고 쓸 수 있음

=> B - Tree가 적합
(해당 key로 검색을 하기에,
depth가 적을수록 유리하다)
(B - Tree는 오름차순으로 키를 정렬하며,
M차 Tree로 다수의 자녀 노드를 가지기에
트리의 깊이가 얕은 편)
(탐색 범위가 점점 더 빠르게 좁혀진다는 말과 상통함)
(또한 노드의 데이터 수도 1개가 아닌 점도 존재함)
(-> 그렇기에 Block 단위로 읽어올때, 같은 노드의 데이터를
들고올 가능성도 커진다)

B tree index는
bst에 비하여 Secondary storage에 접근을 적게 하며,
하나의 노드에 여러 데이터가 저장 가능하기에
block 단위로 데이터를 읽어오는 cache 친화적인 자료구조이다

• hash index와의 비교?
  

  hash는 기본적으로 ‘조회’이기에
  해당 요소가 ‘같은지’만 판단이 가능하다
  범위 기반의 탐색과 정렬에는 사용할 수 없음
  (해쉬 테이블의 다음값이 현재 값보다 크거나 작다는 연관성 x)
  (정렬할 일이나, 비교하여 탐색하는 경우가 없는 경우라면 사용가능하다)
  

정리하자면,
데이터베이스 와 ‘파일 시스템’에 효율적인 자료구조 이다