B tree의 특징
이진 탐색 트리(BST)를 일반화한 트리
부모 노드는 자녀 노드를 두 개 이상 가질 수 있다.
노드가 자녀를 x개 가졌다면 key는 x-1개를 가진다.
노드 내의 key들은 오름차순으로 저장된다.
모든 leaf 노드들은 같은 레벨에 있다.
B tree 데이터 삭제
* 삭제도 항상 leaf 노드에서 발생한다.
* 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
1. key 수가 여유 있는 형제의 지원을 받는다.
2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.
* internal 노드 데이터 삭제 : leaf 노드에 있는 데이터(선임자나 후임자)와 위치를 바꾼 후 삭제한다.
'공부 기록 > 영상 후기' 카테고리의 다른 글
| DB 인덱스(DB index) !! 핵심만 모아서 설명합니다 !! (0) | 2023.03.27 |
|---|---|
| (3부) B tree가 왜 DB 인덱스(index)로 사용되는지를 설명합니다 (0) | 2023.03.26 |
| (1부) B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조) (0) | 2023.03.26 |
| 네트워크와 인터넷 개념 설명! 인터넷 동작 방식도 설명! ISP도 설명! (0) | 2023.03.26 |
| WEB2 - OAuth 2.0 : 9.수업을 마치며 (0) | 2023.03.22 |