해당 강의 영상 정리
https://youtu.be/bqkcoSm_rCs?si=Nx7dqp3mvUHWsXpU
인덱스 내용을 보다가 DB의 인덱스 구현에 사용되는 자료구조를 파악해야겠음을 느꼈다.
이진탐색트리 (BST)
이진 트리 기반의 탐색을 위한 자료구조
모든 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가짐
- 자식 노드는 최대 2개까지 가질 수 있어서 '이진' 트리임
- 모든 원소의 키는 유일함
이진탐색트리에서 더 나아가 자식 노드를 3개로 해주고 싶다면?
이와 같은 모양이 될 것이다. 이때 3개의 자식 노드는 이진탐색트리와는 달리 중간 범위가 늘어나면서 저장해줘야하는 값이 기존의 기준 값(k1)을 제외하고 하나(k2)가 더 늘어나게 된다.
이처럼 자식노드가 3개가 되려면 부모노드에 기준값이 2개가 필요하게 되며 이진탐색트리와 동일한 모양과 기능을 유지할 수 있게 되었다. 이러한 논리대로라면, 기준값을 늘려주며 자식노드의 수를 3개 이상으로 설정해줄 수 있다.
- 자식 노드의 최대 개수를 늘리기 위해 부모 노드에 key를 하나 이상 저장
- 부모 노드의 key들을 오름차순으로 정렬
- 부모노드 key들의 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정
이러한 방식으로 이진탐색트리를 확장한 B tree가 되는 것이다.
B tree
위와 같은 이유로 자식 노드의 최대 개수를 직접 설정하고 부모 key를 나열하여 이진탐색트리와 유사하게 사용해줄 수 있게 되었다.
그러므로 자식 노드의 개수를 직접 지정해주는 과정이 필요하며, 최대 M개의 자식을 가질 수 있는 B tree를 M차 B tree 라고 한다. 위의 예시는 3차 B tree가 될 것이다. 각 노드에 담기는 key의 개수는, 기준값이므로 자식 노드 수보다 1개가 적은 M-1 개가 될 것이다.
- M : 각 노드의 최대 자식 노드 수
- M-1 : 각 노드의 최대 key의 수
- ┌M/2┐(올림) : 각 노드의 최소 자식 노드 수 (루트,리프노드 제외)
- ┌M/2┐-1 : 각 노드의 최소 key 수 (루트노드 제외)
내부 노드의 key 수가 x개 라면 자식 노드의 수는 언제나 x+1 이다
위와 같은 규칙이 적용되므로 부모 노드의 기준키가 2개일 때 자식노드는 무조건 3개가 되어야 한다. 여기서 추론할 수 있는 점은 노드가 최소 하나의 key를 가지므로 몇 차 B tree인지와 무관하게 내부 노드는 최소 두 개의 자식 노드를 가지게 된다.
B tree 탐색
루트 노드부터 시작하여 하향식으로 탐색한다.
루트노드 탐색 -> 키를 찾으면 종료/키를 못 찾았으면 노드 안의 키와 비교하여 자식 노드를 차례로 탐색 -> 리프노드에 도달할 때까지 반복
B tree에 데이터 삽입
- 항상 리프 노드에 삽입한다. 즉 탐색 과정과 반대로 상향식으로 진행된다.
- 노드가 넘치면 가운데 key 를 기준으로 좌우 key 들은 분할하고 가운데 key는 승진(부모노드로 격상)한다.
B tree 데이터 삭제
- 항상 리프노드에서 삭제한다. (상향식으로 진행)
- 삭제 후 최소 key 수 보다 적어졌다면 재조정한다. (최소 key 수: ┌M/2┐)
- 재조정할 땐 왼쪽을 기준으로 삼는다.
재조정 과정
- key 수가 최소 key 수보다 많으면 여유있는 형제의 지원을 받는다
- 만약 여유가 없다면 부모의 지원을 받고 형제와 합친다(삭제할 노드 안에 다른 key가 없다 삭제된다)
- 부모의 지원으로 부모에 문제가 생기면 거기서 다시 재조정한다
혹여 내부 노드의 데이터를 삭제하게 된다면
리프노드에 있는 데이터(아래의 선임자, 후임자에 해당)와 위치를 바꾼 후 삭제해주고 위의 재조정 과정을 거친다. 다만 리프노드에 있는 데이터 중 어떤 데이터와 위치를 바꿔줄 것인지가 중요한데, 결론부터 말하자면 삭제할 데이터의 선임자나 후임자와 위치를 바꿔줘야 한다. 그 이유는 위에서 기재한 여러 규칙들을 만족하는 값이 되기 때문이다.
선임자: 삭제할 데이터보다 작은 데이터들 중 가장 큰 데이터 => 삭제할 노드의 왼쪽 자식 노드의 오른쪽 자식 노드 중 리프노드의 가장 오른쪽 키
후임자: 삭제할 데이터보다 큰 데이터들 중 가장 작은 데이터 => 삭제할 노드의 오른쪽 자식 노드의 왼쪽 자식 노드 중 리프노드의 가장 왼쪽 키
B tree 와 DB Index
B tree와 BST 의 시간복잡도는 같지만...
O(logN) 으로 시간복잡도가 같지만 DB와 메모리의 특징 때문에 B tree를 사용하게 된다고 한다.
먼저 메모리는 휘발성 메모리인 메인 메모리와 비휘발성 메모리인 2차 메모리(SSD, HDD)로 나뉘어진다. 비휘발성 메모리는 데이터를 처리하는 속도가 느리지만 그만큼 많은 용량을 저장할 수 있다는 이점이 있기에 방대한 양이 존재하는 DB는 2차 메모리에 저장된다.
그리고 2차 메모리의 경우 block 단위로 데이터를 읽고 쓴다. block 은 2의 제곱(4kb, 8kb, 16kb,...)으로 표현되며 데이터를 읽고 쓰는 논리적인 단위이다. 다만 불필요한 데이터까지 읽어올 가능성이 있지만 반대로 생각해보면 연관된 데이터를 모아서 저장해두면 더욱 효율적으로 읽고 쓸 수 있게 되는 것이다.
위와 같은 특성들로 인해 DB에서 데이터를 조회할 때 2차 메모리에 최대한 적게 접근하는 것(속도가 느리므로)이 성능에 좋을 것이다.
왜 DB Index로 B tree 계열이 사용되는가?
위에서 2차 메모리에 접근하는 횟수를 최대한 줄이는 것이 좋다고 했다. 각각의 자료구조를 직접 예시를 들어보면 아래와 같은 결과를 볼 수 있다.
AVL tree Index
값이 5를 찾기 위해 아래와 같은 순서로 2차 메모리에 접근하게 될 것이다.
총 4번의 2차 메모리 접근 후 데이터를 찾아온다.
B tree Index
총 2번의 2차 메모리 접근으로도 동일한 조회값을 얻을 수 있음을 확인할 수 있다.
위의 결과로 트리 구조라는 공통점 아래 자식 노드의 수와 노드 안의 데이터 수에 따라 큰 차이점이 생겼음을 알 수 있다. 즉 자식 노드가 많을수록(기준키가 많을수록) 탐색 범위가 빠르게 좁혀지고 노드 안의 데이터들은 서로 연관된 정보이므로 위에서 언급했던 block 단위의 데이터를 다룰 때 저장 공간 활용도가 좋아서 더욱 효과적인 것이다.
무료로 유튜브에 올라간 강의인데 퀄이 무척 높으니 꼭 영상을 보길 추천한다. 차차 나머지 영상들도 볼 예정이다. 자료구조 설명을 넘 잘해주셔서 이해 안되던 것들도 잘 된다.