오늘은 B-tree에 대해서 보고, DB의 기본 인덱스에서 어떻게 사용되는지 좀 더 명확하게 알 수 있어서 정리하고, 유트브 링크를 첨부하려 한다. 자세하게 설명해주신 유투버 쉬운코드님 감사합니다. 
B 트리는 바이너리 서치 트리와 달리 다수의 자식 노드를 가지는 다진 트리입니다. 이로 인해 B 트리는 대량의 데이터를 효율적으로 관리할 수 있습니다.
B-Tree의 특징
•
노드들은 정렬된 순서로 저장됩니다.
•
노드마다 허용된 최대 자식 수가 있습니다.
•
루트 노드부터 리프 노드까지 모든 경로의 길이가 동일하게 유지됩니다.
•
데이터가 노드에 삽입되거나 삭제될 때, 트리의 균형을 유지하기 위한 재조정이 일어납니다.
B 트리는 대량의 데이터를 효율적으로 저장하고 검색하기 위해 사용됩니다. 트리의 균형을 유지하는 능력으로 인해 검색, 삽입, 삭제 연산의 평균 시간 복잡도가 O(log n)입니다.
B-Tree의 예시
예시 B 트리:
8, 15
/ \
3, 5, 6 18, 20
/ | \ / | \
1, 2 4 7, 10, 12 16, 17 19, 21, 23
Plain Text
복사
위의 그림은 다음과 같은 B 트리를 나타냅니다. 여기서 각 노드는 키 값을 가지며, 각 노드의 자식 수와 허용된 키 범위는 B 트리의 특성에 의해 제한됩니다.
이제 몇 가지 작업을 시각적으로 설명해보겠습니다.
1.
검색: 값 17을 검색한다고 가정해봅시다. 루트 노드부터 시작하며, 루트 노드에는 17보다 작은 값이 있는 오른쪽 자식 노드로 이동합니다. 그리고 나서 해당 서브트리의 노드들을 탐색하며 17을 찾게 됩니다.
2.
삽입: 값 13을 삽입하려고 합니다. 루트 노드부터 시작하며, 13은 15보다 작고 18보다 크므로 중간 서브트리로 이동합니다. 중간 서브트리의 루트 노드에는 13보다 작은 값이 있는 왼쪽 자식 노드로 이동하게 됩니다. 거기서 계속하여 리프 노드까지 탐색하며 13을 삽입합니다.
3.
삭제: 값 6을 삭제하려고 합니다. 먼저 삭제할 노드를 찾습니다. 6은 리프 노드이므로 해당 노드를 삭제하고 부모 노드에서 제거합니다. 그 후에 필요한 재조정이 일어나 트리의 균형을 유지합니다.