BJ.54-1 B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조) - ko

네 반갑습니다 오늘이 영상을 끝까지 보신 후엔

피트리의 개념과 특징을 알게 되고요 그리고 비트리의 데이터를 삽입하는

방식도 알게 됩니다 자 그러면 오늘도 고고싱

먼저 우리가 예전에 배웠던 내용을 복습해 보도록 하겠습니다

과거에 우리는 이진 탐색 트리에 대해서 배웠어요 영어로는 바이너리

서치 틀이라고 하고 줄여서

bst라고 하는데요이 바이너리 서치 트리의 특징은 모든 노드의 왼쪽 서브

트리는 해당 노드의 값보다 작은 값들만 가지고 또 모든 노드의

오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가진다는 그런 특징을

가지고 있습니다 그래서 지금 왼쪽에서도 보시면 가령 지금이 노드를

기준으로 얘는 지금

20을 값으로 가지고 있는데 얘의 왼쪽 서브트리는

20보다 작은 값을 가지고 있고 얘의 오른쪽 서브 트리는

20보다 큰 값을 가지고 있습니다 그 다음에 얘를 기준으로도 살펴보면

얘를 기준으로이 친구의 왼쪽 서브 트리는

5보 작은 값을 가지고 있고 오른쪽 서브

트리는 5보다 큰 값을 가지고 있습니다

그래서 모든 노드에서 이런 특징을 가질 때이 트리를 이진 탐색 툴이라고

하고요 그러면이 이진 탐색 트리는 어떤

특징을 가지고 있냐면 자녀노드는 최대 2개까지 가질 수 있다라는 그런

특징을 가지고 있습니다 그래서 얘의 이름이 이진 탐색 트리인 거죠

파이널이라는 그런 뜻을 가지고 있는게 바로 이런 이유 때문인 겁니다

그러면이 특징을 조금 더 자세히 살펴보도록 하겠습니다 자 보시면 이진

탐색 트리에서는 잔여 노드는 최대 2개까지 가질 수

있다고 했는데요 그런데 여기서 이런 생각이 하나 드는

거죠 어떤 생각이냐면 만약에 자녀노드를 3개까지 가지고 싶다면

그래서 이런 형태로 잔여 노드를 3개를 가질 수 있도록

만들고 싶다면 어떻게 하면 될까 이런 궁금증이 드는 겁니다 그래서 이것을

곰곰히 고민을 해보다가 원래 이진 탐색 트리에서 어떻게

했는지를 생각을 해보게 됐어요 얘를 지금 보게 되면이 노드를

기준으로 왼쪽에는 50보다 작은 값을 가지고

있고 오른쪽에는 50보다 큰 값을 이렇게 가지고

있잖아요 그러면 결국 부모 노드의 값을

기준으로 좌우로 이렇게 나누어져서 그

부모노드의 값에 따라서 왼쪽은 부모노드의 값보다 작은 값들을

가지게 하고 오른쪽은 부모노드보다 큰 값을 가질 수 있도록

그렇게 이진 탐색 트리에서는 노드를 구성하고 있으니까이 아이디어를

여기에서도이 상황에서도 적용해 볼 수 있지 않을까 이런 생각이 드는 거죠

그러면 어떻게 하면 되냐 지금 자녀노드가 3개니까이

각각의 잔여 노드가 가질 수 있는 값에 범위를

결정을 해주는 거죠 그래서 이런 식으로

먼저 왼쪽 잔여 노드를 보시면 얘는 어떤 값이 있다고 했을 때이

값보다 작은 값을 가질 수 있도록 하고 가운데 잔여 노드는 k1보다는

크고 K2 보다는 작은 값을 가질 수 있도록 하고 오른쪽 잔여 노드는

k2보다 큰 값을 가질 수 있도록 이런 식으로

값을 분배해줘서 저장하면 되지 않을까 이런 생각이 드는 겁니다

그러니까 바이너리 서치 트리에서 하는 방식을 응용을 해보는 거죠

그러면 차이점은 뭐냐면 지금 이렇게 3개의

자녀 노드에 저장을 하기 위해서는 k1이라는 값이 필요하고

k2라는 값이 필요하다는 거죠 그러면 결국이 부모 노드에는 하나의 값만

저장하면 되는 것이 아니라 이렇게 K1 값과 K2 값을 같이 저장할 수

있도록 해야 되는 겁니다 그러면 예를 들어서 만약에이

부모노드에 50이라는 값과 80이라는 값이

들어가 있으며이 왼쪽 잔여 노드에는 50보다이 키 값을 기준으로

50보다 작은 값을 가질 수 있도록 하고요 그 다음에이 가운데 참여

노드는이 두 개의 키를 기준으로 50과 80 사이의 값을 가질 수

있도록 하고요 그 다음에 오른쪽 자녀노드는이 80이라는 키 값을

기준으로 80보다 큰 값을 가질 수 있도록 하는 겁니다 그래서이 조건에

따라서 각각의 노드의 값을 임의로 넣어보면

이런 식으로 값이 들어갈 수가 있겠죠 왼쪽 잔여 노드는

50보다 작은 값을 가지고 가운데 자녀 노드는

50과 80 사이 것을 가지고 그 다음에 오른쪽 잔여 노드는 80보다

큰 값을 이렇게 가질 수 있도록 만들어 주는 겁니다 이렇게 하면 이진

탐색 트리와 동일한 형태로 동작을 하면서도 하나의 노드가

잔여 노드의 개수를 2개 이상도 가질 수 있도록

그렇게 만들어 줄 수가 있는 거죠 그러면 사실은 이해하기 쉽게

설명하려고 이렇게 잔여 노드 위주로 설명을 드렸지만

예를 트리로 확장을 해서 생각을 해보면

결국은이 각각의 노드 하나하나를 서브 트리로 바꿔서도 생각해 볼 수가

있는 거잖아요 그래서이 왼쪽 잔여 노드는 사실은 이렇게

서브 트리로 확장해서 생각을 해보면이 왼쪽 서버트리에 있는 값들은

50보다 작은 값들을 항상 가지게 될 거고 마찬가지로이 가운데 잔여 노드도

이렇게 서브 트리로 확장해서 생각을 해보면이

서브 트리에 있는 모든 노드들은 50보다는 크고 80보다는 작은

값들을 가진다고 볼 수 있고이 오른쪽 잔여 노드도

서브트리로 확장해서 생각을 해보면이 오른쪽 서브 트리에 있는 모든

노드들은 80보다 큰 값을 가진다라고 그렇게

확장해서 생각할 수가 있는 겁니다 그러면

결국 이런 방식으로이 전체 트리를 구성을 해 볼 수가 있는 거죠 자

그러면 지금까지 배웠던 내용을 정리를 해보겠습니다 우리가 기존에 알고

있었던 바이너리 서치 트리는 각 노드에서

잔여 노드를 최대 2개까지만 가질 수 있었어요

그런데 얘를 확장을 하고 싶었던 거죠 그래서 자녀노드의 최대 개수를 늘리기

위해서 그러니까 지금 이런 상황에서는 현재

자녀 노드가 두 개가 있는데 두 개가 아니라 이렇게 3개로 만들어 주고

싶다면 이것을 위해서 우리가 먼저 해줘야 됐던 것은이 부모노드의 키를

하나 이상 저장할 수 있도록 해줘야 했습니다 그래서이 부모노드에

K1 K2 이렇게 두 개의 키 값을 저장을 하고 그리고 이때 어떻게

저장을 하냐면이 키들을 오름차순으로 정렬을 해서 저장을 해줍니다 이렇게

오름차순으로 정렬을 해줘야이 정렬된 순서에 따라서

잔여 노드들의 키 값도 그 범위가 결정이 될 수가 있어요 그래서 지금

이렇게 순서대로 K1 K2 값이 정렬이 되어

있는 거라면 그러면 이제이 세 개의 그냥 노드들이 가질 수 있는 값의

범위는 이런 식으로 순서대로 그 값의 범위를 가질 수가

있는 거죠 그래서 이런 형태로 동작하는 틀이이 트리를 뭐라고 하냐면

바로 비틀이라고 부릅니다 그러면 지금 우리가 봤었던 이런

방식을 통해서 트리를 구성을 하게 되면

얘는 잔여 노드의 최대 개수를 입맛에 맞게 정해서 쓸 수가 있습니다

그래서 바이너리 서치 트리와 비교를 해보면 바이너리 서치트리는 최대

2개까지 잔여 노드를 가질 수 있었지만이 비트리 같은 경우에는

트리를 구성하는 방식이 바이너리 서치 트리와 매우 유사하면서도

동시에 최대로 가질 수 있는 잔여 노드의 개수를

원하는만큼 결정해서 쓸 수 있기 때문에이 비트리를 바이너리 서치

트리를 1번화한 형태의 틀이다라고도 많이 얘기를 합니다 이해가 되시죠 자

그러면 자녀노대 최대 개수를 우리가 결정해서 쓸 수 있다는게이 비트리의

특징이기 때문에 결국 비트리를 사용을 할 때 최대 몇

개의 잔여 노드를 가질 수 있도록 할 것인가가 중요한 파라미터가 됩니다

그래서 지금부터는 비트리에 어떤 파라미터가 있는지 그것을 좀

살펴보도록 하겠습니다 먼저 지금까지 살펴봤던 것처럼 가장

중요하고 또 핵심이 되는 파라미터는 바로이 파라미터입니다 비트리의 각

노드에서 최대로 가질 수 있는 잔여 노드 수를 몇 개로 할 것인가

이게 가장 중요한 또 근본이 되는 파라미터가 돼요 그래서 얘를 m이라고

표기를 하고요 그러면 비트리를 부를 때 최대 m계의

자녀를 가질 수 있는 비트리를 뭐라고 부르냐면

m 차 피트리라고 부릅니다 그래서 만약에 오른쪽에서 보시는 것처럼 최대

3개의 잔여 노드를 가질 수 있는 비트리가 있다라고 한다면

그러면 그 피트리는 3차 피트리라고 부를 수가 있는 거죠 그래서 비트리를

사용을 할 때이 빅토리에서 최대 몇 개의 잔여 노드를 가질 수 있도록 할

것인가 이게 가장 중요한 파라미터가 되고요

그러면 여기서부터 파생되는 파라미터들이 있는데 그것을 하나하나씩

살펴보면 먼저 각 노드에서 가질 수 있는 최대

키의 수가 또 있습니다 이 파라미터는 우리가 결정하는게 아니에요

얘를 결정하면 자연스럽게 결정이 되는 값입니다 왜냐하면이 파라미터의 값은

앞에서 결정한 그 m의 값의 하나를 뺀 값이 되는 거거든요 그래서 지금

오른쪽에서 보시면 얘가 만약에 3차 비트리다 즉이

피트리는 최대 3개의 잔여 노드를 가질 수 있다라고 한다면 이때이

빅토리에서 각 노드가 가질 수 있는 최대 키의

수는 3에서 1을 뺀 2 즉 각 노드는 최대 2개의 키를 가질 수

있다 이렇게 볼 수가 있는 거죠 사실 이거는 조금만 생각을 해보면 이해를

할 수가 있는 부분인데 왜냐하면 지금 자녀노드의 값의 범위를 이런 식으로

결정을 해주기 때문에 이렇게 세 개의 잔여 노드를 가지려면

키는 두 개가 있어야 되잖아요 만약에 4개의 잔여 노드를 가지도록 만들고

싶다면 그때는 키가 3개까지 필요할 거고요 그래서

결국이 m이라는 값에서 하나를 뺀 값 그만큼이 각 노드가 최대로 가질 수

있는 키의 수다 그렇게 보시면 되겠습니다 그 다음에 또 다른

파라미터는 뭐가 있냐면 각 노드가 가질 수 있는 최소한의 자녀 노드 수

이게 또 파라미터로 있습니다 그런데이 파라미터도 마찬가지로

입간만 사용할 때 결정을 해주면이 값에 따라서 자동적으로 결정이 되는

값입니다 그런데 지금 보시면 이런 기호가

보이잖아요 얘는 뭐냐면은

울림을 해주라는 겁니다 그래서 만약에 3차 비트리다 하면은 m은 3이라는

거잖아요 그러면은 3을 2로 나누면 1.5가 되는데이 1조모는

소수점이라서이 값을 무조건 올림을 해주라는 겁니다 지금 지붕이 뚫려

있죠 그래서 위로 올려 칠하는 얘기고요

그렇게 하면 얘는 최종적으로 2라는 값이 나오기 때문에

결국이 3차 비트리에서 각 노드의 최소 잔여 노드 수는 2개

2개가 되는 겁니다 그런데 여기서 중요한 것은

얘 같은 경우에는이 조건은 루트 노드나 리프 노드에서는 제외가

되는 조건입니다 일단 리프 노드는 잔여 노드가 없는 것을 리프 노드라고

하기 때문에 당연히 제외가 될 거고요 그 다음에 루트 노드 같은 경우에는

출발점이 되는 있어서 얘 같은 경우에는이 조건을 만족하지 않아도

괜찮아요 하지만 나머지 노드들 리프 노드도 아니고 루트 노드도 아닌

나머지 노드들은 비트리에서는 이런 조건을 만족하도록 그렇게 동작을 하게

됩니다 자 그리고 다음 파라미터는 각 노드가 가질 수 있는 최소한의

키수에요 그러면이 파라미터도 우리가 사용할 때 정해주는 값이 아니라

얘만 정해주면 얘에 의해서 자연스럽게 결정이 되는

값입니다 그러니까 아까 바로 앞에서

각 노드의 최소한의 잔여 노드 수가 이렇게 정해진다고 했잖아요

그러면 결국 얘를 바탕으로 최소한의 키스는이 값에서 1을 뺀 값이 바로이

최소한의 키의 수가 되는 겁니다 그래서 보시면이 두 개가 유사하고이

두 개가 유사해요이 두 개는 최대와 관련된 파라미터구요이 두 개는 최소화

관련된 파라미터입니다 그리고 처음이 파라미터만 우리가 사용할 때

정해주면 되는 거고 나머지 파라미터는이 값이 정해지면 자연스럽게

알아서 결정이 되는 값들이다 그렇게 이해를 해주시면 될 것 같아요 아

그리고 참고로이 파라미터 같은 경우에는

루트 노드는 제외가 됩니다 루트 노드 같은 경우에는

처음 데이터가 들어갈 때 루트 노드부터 들어가기 때문에이 조건을

만족하지 않을 수도 있는 거거든요 그래서 루트 노드는 제외가 된다

그렇게 이해를 해주시면 될 것 같습니다 자 그래서 지금까지 이렇게

비트리와 관련된 4개의 파라미터를 살펴봤는데요 사실 비트리를 설명하는

여러가지 방식들이 있고 저 같은 경우에는

각 노드의 최대 잔여 노드 수를 얘를 근본이 되는 가장 기본이 되는

파라미터로 보고 얘를 바탕으로 나머지 파라미터들을

이렇게 자연스럽게 결정하고 계산해 줄 수 있도록 그렇게 설명을

했었는데요 사실 설명하는 방식에 따라서는

어떤 파라미터를 기준 파라미터로 잡을지 다를 수가 있습니다 그래서

저는 얘를 기준으로 설명을 드렸지만 다른 관련 문서를 보시면

얘를 기준 파라미터로 잡고 설명할 수도 있고요

혹은 심지어 얘를 기준 파라미터로 잡고 설명할 수도 있습니다 하지만

제가 봤을 때는 얘를 기준 파라미터 설명할 때 가장

명확하다는 생각이 들어서 저는 얘를 기준으로 설명을 드리게 됐어요

그래서이 부분을 참고를 해주시면 좋을 것 같습니다 자 그러면 비트리와

관련된 또 다른 특징을 하나 살펴보면 자 지금 오른쪽에 이런 형태로

노드들이 구성이 되어 있는데요 비트리에서 이런 형태를 가질 수

있을까요 사실 비트리에서는 이런 구조를 가질 수가 없습니다 왜냐하면

비트리의 인터널 노드 같은 경우에 만약에 그 노드의 키예수가 x개라면

그 노드의 잔여 노드의 수는 언제나 x+1개여야 한다는 그런 특징이 있기

때문에 그래요 그런데 지금 보시면 부모 노드의

키에서는 두 개인데이 부모노드의 자녀 노드의 수도 두 개인 거잖아요 그래서

지금이 상태는이 규칙을 위반하고 있기 때문에 사실 피트리에서는 이런 형태는

나올 수가 없습니다 그럼 제대로 된 형태는 뭐냐 지금 부모노드의 키가 두

개가 있기 때문에이 규칙에 따라서 두 개의 한계를 더한 총 3개의 잔여

노드가 있어야 되고 결국 이런 형태가 돼야 얘가 정상적인

형태가 되는 거죠 그래서 비트리에서는 리프 노드를 제외하고 그 트리에

인턴을 노드들은 그 노드의 키의 수가 만약에 x 계라면 그 노드의 잔여

노드의 수는 언제나 x+1개다 이런 특징을 가진다 그렇게 이해를 해주시면

좋을 것 같고요 그러면 테스트 삼아서 만약에 이런

구조가 피트리에서 가능할까요 얘도 마찬가지로 불가능하겠죠 왜냐하면

지금 부모 노드의 키는 1개인데 자녀노드는 세 개인 거잖아요 그래서

이런 구조는 불가능하고 제대로 된 구조가 되려면 이러한 형태의 구조가

돼야 됩니다 그래서 키가 하나기 때문에

잔여 노드는 이렇게 두 개가 돼야 되는 거죠 그래서 다시 한번 강조를

하면이 비트리에서는 만약에 어떤 인턴을 노드의 키의 수가 x계라면 그

노드의 잔여 노드의 수는 언제나 x+1개다 이것 또한 잘 기억을 해

주시면 좋을 것 같습니다 그리고이 특징을 바탕으로

어떤 결론을 도출해낼 수 있냐면 자 어쨌든 각 노드마다 최소한 하나의

키는 가져야 될 거잖아요 비어있는 노드는 있을 수가 없으니까 최소한의

키는 가져야 될 거기 때문에 그렇다면 여기서 우리가 추론해 볼 수

있는 것은 몇 차 비트리인지와 상관없이이 비트리의 인턴을 노드는

최소한 두 개의 자녀는 항상 가진다 이렇게 말할 수가 있는 겁니다 그리고

만약에 이제 몇 차 비틀인지가 정해지면 최대 몇 개의 잔여 노드를

가지는 비트리로 만들 것인지 그렇게 m이 정해지면

루트 노드를 제외하고이 빅토리의 인턴을 노드는 최소 아까 봤었던이

조건이 조건 만큼의 잔여 노드를 가질 수 있게 된다

그렇게 말할 수가 있는 겁니다 그래서 예를 들어서 만약에 내가 오차

비트리를 사용을 할 거야 그러면이 오차 비트리에서는

루트 노드를 제외하고는 모든 인터널 노드는

5를 2로 나눈 값을 올림 한가 즉 최소한 3개의 자녀 노드를 가질 수

있게 된다 그렇게 생각을 해주시면 될 것

같습니다 그래서 헷갈리지 말라고 설명을 드린 거예요 지금이 얘기는

여차인지 정해지기 전에 일반적으로 몇 차든 상관없이이 피트리에서는 인터널

노드는 최 두 개의 자녀를 가지게 된다는 그것을 설명을 드렸던 거고이

m 값이 정해지면 그래서 구체적으로 몇 차 비트리를 사용할 것인지가

정해지면 그때 실제로 이제 인턴을 노드의 최소 잔여 노드의 개수는 이런

식으로 정해진다 그것을 설명드리려고이 두 개의 문장을 쓰게 된 겁니다 자

그러면 이제부터 비트리의 데이터 삽입이 어떻게 일어나는지를

살펴보도록 하겠습니다 비트리의 데이터를 삽입하기 위해서는

첫 번째로 기억을 해주시면 좋은 부분은

데이터에 추가는 항상 리프 노드에서

발생한다 이것을 먼저 기억을 해주시면 좋고요 그 다음에

데이터가 추가가 됐을 때 그 노드가 넘치면 가운데 키 값 그러니까

순서대로 정렬이 되어 있다고 했잖아요 그렇게 키들이 순서대로 정렬이 되어

있을 때의 가운데 값 영어로는 메디안이라고도 하고 우리말로는

중앙값이라고도 하는데요 그 가운데 키 값을 기준으로

좌우 키드를 분할을 시킵니다 그리고 그 가운데 있었던 그 키 그 키는

승진을 시켜요 그래서요 두 개를 기억을 해 주시면 비트리에서 데이터

삽입이 어떻게 일어나는지 대충 기억을 하실 수가 있을 겁니다 자 그러면

여기서 노드가 넘친다라는 말은 무슨 말이냐 아까 우리가

각 노드가 가질 수 있는 최대 키 값을 어떻게 계산하는지를 살펴봤잖아요

예를 들어서 m 차 비트리라고 하면이 m 차라고 할 때이 m이 의미하는

바는 그 B 트리가 가질 수 있는 최대 잔여 노드스라고 했으니까

그러면이 m을 바탕으로 각 노드가 가질 수 있는 최대 키의

수는 m에서 1을 뺀 값이 값이 최대 키 값으로 가질 수 있는 값이라고

했었죠 그러면 노드가 넘친다라는 말은 하나의 노드에서

m- 한 개보다 더 많은 수의 키를 저장을 하고 있다 그것을 의미하는

겁니다 이거는 뒤에서 예를 따라가 보시면

무슨 말인지 충분히 이해가 되실 거예요 자 그러면 이제 우리가 데이터

삽입을 해 볼 건데요 최대 몇 개의 잔여 노드를 가지도록 할 것인가

그것을 정해줘야 이제 예제를 볼 수가 있어서 지금이 예제에서는 3차 비트를

예로 들어서 살펴보도록 하겠습니다 그러니까 최대 3개의 잔여 노드를

가질 수 있는 그 비트리를 예로 들어서 데이터 삽입이 어떻게 되는지

살펴보도록 할게요 제일 먼저 1을 추가를 해볼게요 지금 아무것도 없는

상태이기 때문에 루트 노드를 만들고 거기에 1을

추가를 해줍니다 그래서 지금 이렇게 1이 추가가 되어 있는 것을 보실

수가 있죠 여기서 보시면은 지금 키를 저장할 수 있는 공간이 총 2개인

거잖아요 왜 이게 두 개인 건지는 이해가 되시죠 왜냐하면 지금 저희가

3차 피트리를 가지고 예를 들고 있기 때문에 최대 3개의 잔여 노드를 가질

수 있으니까 최대로 가질 수 있는 키의 수는 3에서 1을 뺀 값인 2개

2개를 최대로 키로 가질 수 있기 때문에 지금이 그림에서 두 개의 키를

저장할 수 있는 공간을 이렇게 마련을 해둔 겁니다 이해가 되시죠 자 그러면

1을 추가하는 것은 이렇게 끝이 났고 이제 15를 추가를 해보겠습니다

그러면 아까 우리가 기억을 해야 되는 것은 추가는 항상 리프 노드 한다고

했잖아요 지금 얘는 루트 노드이기도 하지만 어떻게 보면 리프 노드라고도

볼 수 있기 때문에 일단 여기에 추가를 해줍니다

그런데 지금 보시면 비어 있는 공간이 하나 있기 때문에 여기에다가 이렇게

15를 하나 추가를 해주면 됩니다 자 그리고 참고로 지금 조금 글자가 작아

보일 수가 있어요 특히나 핸드폰으로 보시면

조금 작아 보일 수가 있는데요 얘가 지금 예제가 많아서 계속해서 확장이

될 거라서 지금은 이렇게 작아 보이지만 나중에는이 전체 화면이 꽉

찰 거거든요 그래서 그 부분을 조금 이해를 해 주시고 봐주시면 좋을 것

같습니다 자 지금 15 추가는 그러면 이렇게 끝이 났고요이어서 2를 추가를

해보도록 할게요 그러면

추가는 일단 항상 리프 노드에 한다고 했잖아요

얘가 여전히 아직 루트 노드이면서도 리프 노드니까 여기에다가 2를 추가를

할 건데 이때 중요한 것은 뭐냐면 추가를 할 때 오름차순으로 정렬이

돼서 추가가 될 수 있도록 그렇게 저장을 해 줘야 됩니다

그러면 지금 이미 1과 15가 있기 때문에 정렬된 형태로 저장을 해주면

이런 형태로 저장이 될 겁니다 그런데

문제가 하나 생겼죠 원래 최대 2개까지 저장을 할 수가

있는데 지금은 3개가 저장이 되어 있는 거예요 즉

노드가 넘친 겁니다 그러면 노드가 넘치면 어떻게 해야 되냐면 가운데

키를 기준으로 좌우 키드를 연결시키고 가운데 키는

승진을 시켜 줘야 돼요 그러면 지금 얘가 가운데 값이니까이 2는 승진이

돼야 되고 나머지 좌우에 있는 키들은 분할이 되어야 합니다

얘를 분할을 시키는게 좀 더 매끄럽겠죠 일은 그냥이 자리에 가만히

있으면 될 것 같고 15를 따로 떼어내보면 이렇게 노드를 하나 만들고

여기에 있던 15를 이렇게 이쪽으로 옮겨줍니다 그 다음에 2는 승진을

시켜 줘야 되기 때문에 상위 레벨에 노드를 하나 만들고 2를 이쪽으로

이렇게 승진을 시켜줍니다

그러면 이렇게 승진이 된 예에는 아까 좌우로 나누어진이 각각의 키들을

왼팔 오른팔로 이렇게 가지게 됩니다 그래서 지금 이렇게 표시되어 있는이

부분 있잖아요 얇은 막대기처럼 보이는이 부분이

사실은 잔여 노드들을 가리키는 포인터 역할을

한다 그렇게 보시면 될 것 같습니다 자 이번에는

5를 추가를 해보겠습니다 5를 추가한다는 것은 결국

5를 어디에 넣어야 될지 그 리프 노드를 찾아야 되는 거거든요 그 말은

결국 빅트리에서

교회를 해야 된다는 것과 같은 의미이기 때문에 조회에 출발은 항상

루트 노드에서 시작을 하는 거거든요 자 그러면 일단 2와 5를 비교를

해요 그런데 5가 더 크잖아요 그러면 이쪽으로 빠집니다

그런데 여기서 리프 노드를 만났잖아요 그러면 여기에다가 5를 추가를 해줘야

되는데 정렬된 형태로 추가를 해줘야 되기 때문에

실제로 저장이 됐을 때는 이런 형태로 오름차순으로 저장이 될 겁니다 그러면

이제 5에 대한 추가는 끝이 난 거예요 이제는 30을 추가해 보도록

하겠습니다 일단 30을 루트 노드에 있는 얘와 비교를

해요 근데 30이 더 크니까 이쪽으로 빠지겠죠

그런데 얘가 리프 노드니까 여기에 이제 30을 추가를 해줍니다 그래서

이렇게 32 추가가 됐어요 정렬된 형태로 추가가 됐습니다

그런데 문제가 생겼어요 노드가 넘쳐 버린 거죠 원래

2개까지만 저장할 수 있는데 지금 3개가 된 거예요

그러면 이제 분할을 시켜 줘야 됩니다

30과 5를 좌우로 분할을 해줘야 되고 가운데 있는이 15는

승진을 시켜 줘야 돼요 그러면 그 과정을 또 수행을 해보면 자 얘 두

개를 분할을 시켜 줘야 되는데 쉽게 하기 위해서이

떼어내 보겠습니다 그래서 이렇게 새로운 노드 하나를 만들고요

30을 이쪽으로 이렇게 옮겨줍니다 그리고 얘가 이제 승질을

해야 되잖아요 그러면 이제이 부모노드로 승진이 되는

거거든요 한 단계 위 레벨로 승진해야 되기 때문에 부모노드로 승진을 하게

되는 건데 부모노드에 지금 공간이 하나가 비어 있기 때문에 15를

이제이 위치로 승진을 시켜서 좌우로 나누어진 이키들에 대해서는

이렇게 아래쪽 잔여 노드들로 가질 수 있도록 해주는 거죠 그러면 이제

30에 대한 추가는 끝이 난 거예요 이제 90을 추가를 해보도록

하겠습니다 그러면 90에 대해서 루트 노드와

먼저 비교를 하는데요 이와 먼저 비교를 하는데 이보다 90이 더 크고

그런데 바로 옆에 15가 있기 때문에 15와 90을 비교를 하는데 여전히

90이 더 커요 그러면 이쪽으로 가겠죠 그래서 이쪽으로 왔더니 얘가

리프 노드네요 그러면은 얘의 이제 추가를 해줘야 되는데

여기에 빈 공간이 있기 때문에 바로 이렇게 90을 추가를 해줍니다 바로

추가를 해줘도 정렬된 형태로 유지가 되는 거죠이어서 20을 추가를

해볼게요 그러면 20과 2를 먼저 비교를 합니다

20이 더 커요 그런데 또 15가 있네요 그러면 15와 20을 비교를

하는데 여전히 20이 더 큽니다 그러면이 오른쪽으로 가야 되겠죠

그런데 얘가 리프 노드니까 이제 여기에 추가를 해줘야 되는데 정렬된

형태로 추가를 해줘야 되니까 20은 30보다도 작잖아요

그러면 결국 23 90 형태로 저장이 돼야 됩니다 그래서 이런 식으로

정렬된 형태로 저장이 됐는데 문제는이 노드가 넘쳐 버렸어요

그러면이 가운데 값을 기준으로 얘와 얘를 분할을 시켜주고 가운데

값인이 30은 승진이 될 수 있도록 만들어 줘야 돼요 자 그러면 이제

분할을 해보면 먼저 얘를 이렇게 떼어내서

새로운 노드에다가 90을 넣어 주고요 그 다음에 얘를 승진시키기 위해서이

부모노드로 올려 줘야 되는데 얘가 지금 이미 꽉 차 있으니까

그래도 일단이 위로 올려야 되거든요 그래서 공간을 이렇게 만들어 주고이

공간에다가 30을 승진을 시켜서 아까 좌우로

분할된 그 키들을 왼팔과 오른팔로 이렇게 가질 수

있도록 해주는 거죠 그러면 이제 이런 상태가 됐는데

얘가 지금 이미 노드가 넘쳐 있잖아요 그러면이 상태에서 또 한 번

분할을 해줘야 됩니다 그러면이 키들에 대해서는 좌우로 나눠주고 가운데

값인이 15에 대해서는 승진이 될 수 있도록 만들어 줘야

되는 거죠 자 그러면 분할을 해보겠습니다

먼저 예를 떼어낸다고 생각을 해보면 이렇게

노드를 하나 새로 만들고요 그 다음에 얘를 이렇게 옮기게 될 텐데 이렇게

옮기면서 결국이 왼팔과 오른팔도 같이 따라오겠죠 그래서 31 이렇게

옮겨줬고 왼팔 오른팔이 다 따라왔습니다 그 다음에 해줘야 되는

것은 얘를 승진을 시켜 줘야 되는데 상위

레벨로 올려 줘야 되는데 지금 상위 레벨에 그 어떤 노드도 없잖아요

그러면은 이렇게 새로운 노드를 하나 만들어 주고

15를 이제이 위치로 이렇게 승진을 시켜줍니다 그래서 이렇게 승진이 되고

나서 이제 뭘 해줘야 되죠 그쵸 나누어진이 키들에 대해서

왼쪽 자녀 오른쪽 자녀가 될 수 있도록 이렇게

연결을 시켜 줘야 됩니다 여기까지 하면 이제 20에 대한 추가는 끝이

난 거예요 자 그러면 이제는 얘가 새로운 루트 노드가 되는 거죠

자이어서 또 진행을 해보겠습니다 이번에는 7을 추가를 해볼게요 그러면

7에 대해서 노트 노드부터 먼저 비교를 해봐야

되겠죠 그러면 15와 7을 비교를 하는데 15가 더 크니까 이번에는

이쪽 방향으로 내려갑니다 여기서 또 얘가 리프 노드가 아니니까이 안에

있는 키들과 비교를 하는데 2와 7을 비교를 해서 7이 더 크니까 이번에는

이쪽으로 갑니다 그러면 이제 리프 노드에 왔어요

여기서 이제 비어있는 공간에 넣어주면 되는데 정렬된 형태로 넣어주면 되는

거죠 이렇게 칠을 넣어주면 그걸로 7에 대한 추가는 끝이납니다이어서

9를 추가를 해볼게요 15와 9를 비교를 하는데 15가 더 크니까

그러면 왼쪽으로 빠져야 되죠 여기서 다시 2와 9를 비교를 하는데

9가 더 크니까 이번에는 오른쪽으로 빠집니다 그래서 리프 노드를 만났어요

그러면 여기에 이제 추가를 해줘요 그래서 이렇게 정렬된 형태로 추가를

해줬는데 문제는 이제이 노드가 다 차서 넘친

거잖아요 그러면 이제

얘네들을 분할을 해줘야 됩니다 가운데 값을 기준으로

좌우 키들은 분할을 해주고 가운데 있는이 7은 승진이 될 수 있도록

만들어 줘야 해요 그러면 일단 얘를 떼내기 위해서 이렇게 새로운

노드에다가 9를 넣어 주고요 그 다음에 얘를 승진 시켜 줘야 되니까

상유 레벨로 그러니까는 부모노드로 올려 줘야 되는데 보시면 부모노드의

비어 있는 공간이 하나 있으니까이 자리에 실은 승진을 시켜서이 7이

두개로 분할된이 키들을 왼쪽 잔여 노드 또 오른쪽 잔여

모드로 가리킬 수 있도록 이렇게 설정을 해줍니다

그러면 9에 대한 추가는 이제 끝이 났고 이제 팔을 추가를 해 볼게요

다시이 루트 노드에서 15와 8을 비교를 해보는데 15가 더 크니까

그럼 이쪽으로 빠지게 될 거고 여기서 이제 또 팔을 비교를 해봐야 되는데

왜냐면 얘가 리프 노드가 아니니까요 그런데 먼저 2와 8의 비교를

해봤는데 8이 2보다 더 크잖아요

그런데이 노드에는 2보다 큰 7이 또 있기 때문에

7과 8을 비교를 해보는데 여전히 827보다 더 큽니다

그러면 이쪽으로 빠지게 되고 여기서 드디어 리프 노드를 만났는데 비어있는

공간이 하나 있어요 그러면 여기에 넣어주면 되는데 정렬된 형태로 넣어

줘야 되기 때문에 최종적으로는 이런 형태로 저장이 됩니다이어서 10에

대한 추가를 해보겠습니다 루트 노드에서 10과 15를 비교를

해보는데 15가 더 보니까 이쪽으로 빠지고 그 다음에 여기서 또 10과

먼저 2를 비교를 하는데 12보다 더 크고이어서 7과 10을 비교를 하는데

이번에도 10이 7보다 더 크니까 이쪽으로 빠지게 돼요

얘는 이제 리프 노드니까 여기에 추가를 해줘야 돼서 정렬된 형태로

추가를 해주면 이런 식으로 저장이 되는데

문제는 이제 넘친 거잖아요 그러면 얘를 또 분할을 해 줘야 됩니다

그래서 가운데 값 중앙값을 기준으로 좌우를 분할을 해주고이 중앙값은

승진이 되도록 만들어 줘야 되는 거죠 자 그러면 먼저

얘를 좀 떼어내보면 이런 식으로 새로운 노드를 만들고 여기에다 10을

저장을 하고요 그 다음에 얘를 승진을 시켜 줘야 되는데 지금 부모노드이

부모노드가 꽉 차 있어서 예비 공간을 일단 만들어 줍니다 그래서 이렇게

예비 공간을 만들어 준이 자리에이 구를 승진을 시켜서 나누어진 좌우

키드를 왼팔과 오른팔이 가리킬 수 있도록

이렇게 만들어 줍니다 그래서 결국 이런 형태가 됐는데

문제는 노드가 넘쳤잖아요 그러면 얘도 또 해결을 해 줘야

됩니다 그래서 그 과정을 또 수행을 해보면 일단 얘를 떼어 하기 위해서

여기에 노드를 하나 새로 만들고요 그 다음에 9를 이쪽으로 이렇게 옮겨 줄

겁니다 이렇게 옮겨 줄 때 왼쪽 자녀와 오른쪽 자녀를 가리키는

얘네들도 같이 옮겨 줘야 되겠죠 그래서 이런 형태로 조정이 되고요 그

다음에 얘를 승질을 시켜 줘야 되는데 지금 보시면은이 부모 레벨로 승진을

시켜 줘야 되는데 여기에 비어있는 공간이 하나가 있어요

그런데 이미 15가 있는데이 15는 7보다 크기 때문에 15를 이쪽으로

한 칸 옮겨 줘야 됩니다 그러면 이때 옮겨 줄 때 15보다 큰 값들은이

노드를 가리키고 있기 때문에 결국 이렇게 옮겨 준다는 것은 이렇게

가리키는 얘도 이쪽으로 이렇게 한 칸 옮겨 줘야 된다는 얘기거든요 그래서이

부분을 먼저 조정을 해주면 15를 이렇게 옮기면서이 오른팔에 대한

부분도 약간 조정을 해줬습니다 그래서 이제이 공간을 확보를 했고 이제 얘를

승진을 시켜서 나누어진 두 키들을 왼팔 오른팔로 이렇게 가질 수 있도록

조정을 해주는 거죠 자이어서 진행을 해볼게요 거의 다 와 갑니다

50을 추가를 해보겠습니다 그러면

시작한다고 했잖아요 50과 7을 먼저 비교를 하는데

50이 더 커요 그런데 7 옆에 15가 있으니까 15랑도 비교를

하는데 15와 비교를 해도 50이 더 큽니다 그러면 이쪽으로 내려와요

여기서 얘가 지금 리프 노드가 아니니까

50과 30을 먼저 비교를 하는데 50이 더 크죠 그러면 이쪽으로

옵니다 여기는 리프 노드니까 이제이 자리에 데이터를 넣어주면 되는데

오름차순으로 넣어 줘야 되기 때문에 이런 형태로

저장이 됩니다이어서 70을 추가를 해볼게요

루트 노드에서부터 시작을 해서 70과 7을 먼저 비교를 하는데

70이 더 커요 그 다음에이어서 15와도 비교를 하는데

여전히 70이 더 큽니다 그러면 이쪽으로 와요 여기서 이제

다시 70과 30을 비교를 하는데 70이 더 큽니다 그럼 이쪽으로 와서

얘는 리프 노드니까 여기에 추가를 해줘야 되는데 정렬된 형태로 추가를

해 줘야 되니까 50 70 90이 순서대로 저장을

해줘야 되잖아요 그래서 이렇게 저장을 해줬습니다

그런데 문제는 여기가 이제 넘쳐 버린 거예요 그러면이 중앙값을 기준으로

좌우로 키를 분할을 해 줘야 돼요 그리고

70은 승진을 시켜 줘야 되는 거죠 그러면

얘를 떼어낸다고 생각을 해보면 이런 식으로

새로운 노드의 90을 넣어주고요 그 다음에 얘를 승진을 시켜 줘야 돼서

부모노드로 한 레벨 올려서 저장을 해주면 됩니다 그래서 여기 비어있는

공간이 있기 때문에 여기에다가 70을 승진을 시켜서 나누어진 두 키들을

왼팔 오른팔로 이렇게 가질 수 있도록 조정을 해주는 거죠 자이어서 60을

추가를 해보도록 하겠습니다 사실 여기서부터 시작을 하는 거죠

7과 60을 비교를 해서 60이 더 크고 15와도 60을 비교를 했는데

60이 더 큽니다 그럼 이쪽으로 가서 다시 또 여기서 진행을 하는 거죠

30과 60을 비교를 했는데 60이 더 커요 그런데

70과 60을 비교를 했는데 이번에는 70이 더 큽니다

그러면은 이번에는 여기로 가는 거겠죠 왜냐하면 60이 30과 70의 사이에

있는 값이니까요 그래서 이쪽으로 왔는데 여기는 리프 노드니까 값을

추가를 해주면 됩니다 정렬된 형태로 값을 추가를 해주면 이제이 위치에

60이 들어가게 됩니다 마지막으로 40을 추가를 해볼게요 그러면 다시

루트 노드에서부터 시작을 합니다 40과 7을 먼저 비교를 해요 그런데

40이 더 큽니다이어서 15와 40을 비교를 해요 그런데도 40이 더

큽니다 그러면 이쪽으로 오겠죠 그 다음에

여기서 또 42 30과 비교를 해요 40이 더 큽니다

70과 비교를 해요 70이 더 커요 그러면 이쪽으로 옵니다

리프 노드니까는 여기에 이제 데이터를 추가를 하면 되는데 이때 정렬된

형태로 데이터를 추가를 해야 되고 그래서 이렇게

4560순으로 저장을 했는데 문제는이 노드가 넘쳐 버린 거예요

그러면 가운데 값을 기준으로 얘와 얘를 분할을 시키고이 50이라는

중앙값은 승진을 시켜 줘야 됩니다 그래서 먼저

분할을 시켜주면 얘를 오른쪽으로 떼어내서 이런 식으로

새로운 노드의 60이라는 값을 저장을 해주고요 그다음에 50이라는 값을

부모노드로 승진을 시켜 줘야 되는데 얘가 지금 꽉 차 있잖아요 그래서

추가로 이렇게 공간 하나를 더 만듭니다 그 다음에 여기서 저장을 할

때도 오름차순 순으로 정렬을 해야 되는데

52의 승진을 할 거기 때문에 그러려면

70이 한 칸 이쪽으로 옮겨 줘야 돼요 그런데 이렇게 옮겨 주려면

70에 오른팔에 해당하는 부분도 같이 이렇게 옮겨 줘야 됩니다 그래서 그

작업을 먼저 이렇게 수행을 하고요 그 다음에 이제 공간이 하나 생겼으니까이

위치에 50을 승진을 시켜서 50의 왼팔과 오른팔이 나누어진

키들을 가리킬 수 있도록 조정을 해줍니다 그래서 결국 이런 상태가

됐는데 공교롭게도 얘도 지금 노드가 넘쳐 버렸어요 그러면 가운데 값을

기준으로 왼쪽과 오른쪽을 또 분할을 해줘야 되잖아요 그래서

70을 일단 떼어내면 이렇게 새로운 노드를 하나 만들고 이제 70을

이쪽으로 옮겨야 되는데 이렇게 옮기면서

왼팔과 오른팔도 같이 이쪽으로 이렇게 옮겨 오겠죠 그래서 이런 식으로

70은 조정이 되고요 그 다음에 얘를 승진을 시켜 줘야 되는데 부모 노드로

올리려고 보니까 여기도 지금 꽉 차 있어요 그래서 일단 추가로 한 칸을

더 만들고요이 위치에 50을 올려줍니다 이제 이렇게 50은 승진이

됐고이 50의 왼팔과 오른팔을 또 이렇게 조정을 해주는 거죠 그러면

최종적으로 이런 상태가 됐는데 얘도 지금

노드가 넘쳤잖아요 그러면 다시 한번 또 분할을 해 줘야

됩니다 그래서 또 그 작업을 수행을 해보면이 50을 떼어내야 되니까

노드를 하나 이렇게 새로 만들고 50을 이쪽으로 옮겨 줘야 되는데

옮길 때이 왼팔과 오른팔도 같이 따라와야 되죠 그래서 이렇게 50을

조정을 해줬고요 그러면 이제 얘를 승진을 시켜 줘야 되는데 상위 레벨에

지금 아무런 노드가 없기 때문에 새로운 노드를 이렇게 하나 만들고

얘를 이렇게 승진을 시켜줍니다 그리고 최종적으로

나누어진 키들에 대해서 승진된 15가

m8과 오른팔을 이렇게 가질 수 있도록 조정을 해주는 거죠 그러면

최종적으로는 이제이 비트리 3차 비트리는 이런 식의 형태를 갖추게

됩니다 그래서 이제 데이터 삽입과 관련된 예제는 모두 끝이 났구요

하나만 비틀의 특징을 설명드리고 마치자면 지금까지 이렇게

쭉 데이터를 삽입하는 예제를 따라오시다 보면은

눈치 빠르신 분들은 이미 아셨을 수도 있는데요이 빅토리에는 어떤 특징이

있냐면 모든 리프 노드들은 같은 레벨에 있다라는 특징이 있어요 그래서

지금도 보시면은 얘네들이 다 리프 노드인데 다 같은 레벨에 있죠 그리고

지금까지 이렇게 트리가 만들어지는 과정 속에서도 보시면은 모든 리프

노드들은 같은 레벨에 있다라는 것을 알 수 있습니다 자 여기서 레벨이라는

것은 참고로 말씀드리면 이렇게이 하나하나가 다 레벨인 거죠 그래서

모든 리프 노드들이 같은 레벨에 있다라는 거 이게 비트리의 특징이고요

그러면 이런 특징을 바탕으로이 비트리는 어떤 틀이다라고 말할 수

있냐면이 피트리는 밸런스드 트리다 즉이 말은 무슨 말이냐 바이너리스

치트리 같은 경우에는 밸런스 트리가 아니거든요

얘는 이런 형태로도 트리가 구성될 수 있기 때문에 최악의 경우에는 시간

복잡도가기구 n이 될 수가 있는데 지금이 비트리 같은 경우에는 이런

식으로 모든 리프 노드들이 같은 레벨이기 때문에이 빅토리에서 검색을

할 때에 에버리지 케이스나 월스트 케이스 모두 시간 복잡도가 비고 로그

n이 된다 그렇기 때문에 조회를 할 때도

항상 일정한 성능을 낼 수 있다 그런 특징을 보이는게 바로이 비트리다

그렇게 이해를 해주시면 좋을 것 같습니다이 시간 복잡도와 관련 2부

영상 끝날 쯤에 전체적으로 다시 한번 간략하게 요약해서 말씀을 드리도록

하겠습니다네 오늘 준비한 영상은 여기까지입니다 1부 영상 같은

경우에는 비트리의 특징을 파악을 하고 또 데이터 삽입이 비트리에서 어떻게

일어나는지를 살펴봤는데요 2부 영상에서는 비트리에서

데이터를 삭제할 때 어떤 식으로 동작을 하는지 그리고 또 비트리에

특징들을 다시 한번 정리해서 설명을 드릴 예정입니다

참고로 노드의 데이터를 추가하고 또 삭제하는

과정 동안에 데이터를 조회하는 일도 같이 일어나기

때문에 삽입이나 삭제를 설명하면서 자연스럽게

조회가 어떻게 되는지도 설명드리도록 하겠습니다 그리고

원래 비트리는 일부 2부로 구성을 하려고 했는데요

총 3부작이 될 것 같아요 3부 영상에서는 왜 DB 인덱스의 비트리

자료 구조가 쓰이는지 정확히 말하면 비트리 보다는 b+2인데 어쨌든 두

개가 되게 유사하고 d+

기반으로 파생된 변형된 틀이기 때문에 그래서 왜

인덱스의 비트리 계열이 데이터 구조로 사용이 되는지를 3부 영상에서는

설명을 드리도록 하겠습니다 자 끝까지 봐주신 모든 분들 정말 최고시구요

저는 또 다음 영상을 준비하러 가보겠습니다

감사합니다