[Data Structure] B-Tree&B+Tree

B-Tree?

• 이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하며, 균형이 맞지 않으면 검색 효율이 선형 검색 급으로 떨어진다.
  • 단, 이진 트리의 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(log N)의 성능을 보이는 장점이 있다.
  • 이러한 장점 때문에 계속해서 개선하고자하는 노력이 이루어지고 있다.
• B-Tree는 이진 트리를 확장해서 더 많은 자식을 가질 수 있도록 일반화하였다.
  • B Tree는 자식 수를 일반화 하면서 하나의 레벨에 더 많이 저장된다.
  • 또한 트리의 균형을 자동으로 맞추는 로직까지 갖추었다. 
  • 균형을 맞추는 로직은 간단하면서 효율적이다.
  • B Tree는 레벨로만 따지면 완전히 균형을 맞춘 트리이다.
• 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다.
• 대량의 데이터를 처리해야할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 큰 장점
  • 대량의 데이터는 메모리보다 블록 단위로 입출력하는 SSD나 하드디스크에 저장해야하기 때문
  • 예) 한 블록이 1024바이트의 경우 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용이 발생한다. 따라서 하나의 노드에 1024 바이트를 꽉 채워서 조절할 수 있다면 입출력에 있어 효율적인 구성을 갖출 수 있다.
  • B Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용되고 있다.
• B-트리는 하나의 노드에 여러 자료가 배치되는 트리 구조이다.
  • 하나의 노드에 M개의 자료가 배치되면 M차 B 트리라고 한다.
  • 5차 B 트리의 경우 자식 노드가 최대 5개인 것을 의미한다.
• B-트리의 스스로 균형을 맞추는 특성 때문에 최악의 상황에서도 O(log N)의 성능을 보인다.

B-Tree 규칙

• 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
• 각 노드의 자료는 정렬된 상태여야함
• 루트 노드는 적어도 2개 이상의 자식을 가져야함
• 외부 노드로 가는 경로의 길이는 모두 같음.
• 입력 자료는 중복 될 수 없음
• B-Tree는 최대 M개의 자식을 가질 수 있다. 이를 M차 B Tree라고 한다.
  • 노드는 최대 M개의 자식노드를 가질 수 있다.
  • 노드에는 최대 M-1개의 Key를 가질 수 있다.
  • 루트 노드와 리프 노드를 제외한 각 노드는 최소 M/2개의 자식 노드를 가진다.
  • 루트 노드를 제외한 각 노드는 (M/2)-1개의 키를 가진다.
  • internal 노드의 key가 x개인 경우 자녀 노드의 수는 언제나 x+1개이다

B-Tree 데이터 삽입

• 데이터 추가는 항상 leaf 노드에 한다.
• 노드가 넘치면 가운데 key를 기준으로 좌우 key를 분할하고 가운데 key는 승진한다.
  • 노드가 넘치는 것은 각 노드는 M-1개의 key를 가질 수 있는데 데이터 삽입 과정에서 이를 위반한 것
• 삽입에 관한 규칙은 다음과 같다.
  • 트리가 비어있다면 루트 노드를 할당하고 K를 삽입한다.
  • 트리가 비어있지 않다면, 데이터를 삽입할 적절한 leaf 노드를 탐색한다.
  • 리프 노드에 데이터를 넣고, 리프 노드가 적절한 상태에 있다면 종료한다.
  • 리프 노드가 부적절한 상태에 있다면 분할한다.

분할이 일어나지 않는 경우

• 리프 노드가 넘치지 않았다면, 오름차순으로 K를 삽입한다.

분할이 일어나는 경우

• 만일 리프 노드에 key 노드가 가득 찬 경우, 노드를 분할해야 한다.
• 노드가 넘치면 가운데 key를 기준으로 좌우 key를 분할하고 가운데 key는 승진한다.

 

 

B Tree 데이터 삭제

• 삭제도 항상 리프 노드에서 발생한다.
• 삭제 후 최소 key 수 보다 적어졌다면 재조정한다.
• 재조정 과정은 다음과 같다.
  1. key 수가 여유있는 형제의 지원을 받는다.
  2. 1번이 불가능하다면 부모의 지원을 받고 형제와 합친다.
  3. 2번후 부모에 문제가 있다면 거기서 다시 재조정한다.

리프 노드에서 삭제 후 재조정 할 필요 없는 경우

• 단순히 삭제 후 종료한다.

리프 노드에서 삭제 후 재조정 해야 하는 경우

• key 수가 여유있는 형제의 지원을 받을 수 있는 경우
• 31을 삭제하기 위해선 최소한의 키수보다 작아지기 때문에 재조정을 해야한다.
• key 수가 여유있는 형제의 도움을 받는다.
  • 먼저 동생(왼쪽) 노드를 보면 키가 25, 28로 여유가 있기 때문에 동생 노드로 부터 키를 지원 받는다.
  • 바로 28로 옮기는 것이 아닌 B트리의 속성에 맞게 28은 부모 노드로 옮기고 30을 내린다. 

• 위 과정을 거친 후 부모에서도 문제가 생겼다면 거기서 다시 재조정을 진행한다.
• 부모가 루트 노드가 아닌 경우
  • 그 위치에서 부터 다시 1번 과정을 진행
• 부모가 루트 노드이고 비어있는 경우
  • 부모 노드를 제거
  • 직전에 합쳐진 노드가 루트 노드가 된다.

internal 노드에서 데이터를 삭제하는 경우

• internal 노드에 있는 데이터를 삭제하기 위해선 리프 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
  • 이후 재조정 과정을 거친다.
• 어떤 위치에 있는 리프 노드와 위치를 바꿀까?
  • 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.
  • 선임자(predecessor) : 나보다 작은 데이터들 중 가장 큰 데이터
  • 후임자(successor) : 나보다 큰 데이터들 중 가장 작은 데이터
• 33을 삭제할 때 , 33은 리프 노드가 아니기 때문에 33의 선임자를 찾는다. 33의 선임자는 32이기 때문에 32와 위치를 바꾸고 삭제를 진행한다.

B+ 트리?

• B트리는 특성상 순회 과정이 상당히 난감하다.
• B+트리는 색인 구조에서 순차 접근에 대한 문제의 해결책으로 제시되었다.
• B-트리에서는 특정 key 값이 하나의 노드에서만 존재할 수 있지만, B+ 트리에서는 leaf 노드와 leaf의 부모 노드에서 공존할 수 있다.
  • B+ 트리의 비단말 노드(not leaf)들은 데이터의 빠른 접근을 위한 인덱스 역할만 하기 때문이다.
  •  leaf 노드들은 연결 리스트 형태로 서로 연결되어 있다.
• 기존의 B Tree와 데이터의 연결리스트가 결합되어 구현된 색인구조이다.

B+트리의 장단점

장점

• 블럭 사이즈를 더 많이 이용할 수 있음
  • key 값에 대한 하드디스크 액세스 주소가 없기 때문
• leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리함

단점

• B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함

B+트리 데이터 삽입

• B-tree와 거의 동일하게 이루어진다.
• 노드의 분열이 일어나면 중간 key 값이 부모 노드로 올라갈 뿐 아니라 새로 분열된 노드에도 포함되어야 한다.
• 새 노드는 leaf 노드끼리의 linked list에도 삽입되어야 한다.

B+트리 데이터 삭제

• 재배치와 합병이 필요하지 않을 때는 leaf 노드에서만 삭제된다
• Index 부분은 다른 key 값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않는다.
• 재배치할 경우 index 부분의 node의 key 값은 변하지만 tree 구조는 변하지 않는다.
• 합병을 할 경우 index 부분에서도 key 값을 삭제한다.

B-Tree & B+ Tree

• B-tree는 각 노드에 데이터가 저장됨
• B+tree는 index 노드와 leaf 노드로 분리되어 저장됨
  • (또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)
• B-tree는 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있음
• B+tree는 각 노드에서 key만 들어감. 따라서 data는 모두 leaf 노드에만 존재
• B+tree는 add와 delete가 모두 leaf 노드에서만 이루어짐

 

 

 

 

 

출처

https://wangin9.tistory.com/entry/B-tree-B-tree

[파일구조] B tree 와 B+ tree

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정

 

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖