[모호하면 바로] 인덱스가 왜 B트리를 사용할까?

 

배경

인덱스에는 B트리, 혹은 B트리의 변형인 자료구조가 사용됩니다. 그 이유를 설명해 보세요.

나 왜 이거 대답 못해..? 쭈글..

 

B 트리 인덱스의 장점

먼저 인덱스는 데이터베이스 내부에 특정 필드값을 기준으로 정렬된 테이블을 만든다.

말은 테이블이라고 했지만 실제 데이터는 B트리 형태로 저장됨.

 

 

왜 B트리 형식을 사용할까?

B트리는 대용량 데이터에 대해 빠른 탐색이 가능하다.

 

균형 잡힌 구조로 데이터가 정렬된 상태를 유지한다.

트리의 각 노드는 여러개(2개 이상)의 자식 노드를 갖는다.

자식 노드가 여러개 이므로, 일반 트리보다 탐색을 위한 연산 횟수가 적다.

 

아래는 제품 번호(기본키)를 기준으로 인덱스 테이블(B트리형)이 생성된 모습이다.

 

출처 : 이것이 컴퓨터 공학이다

 

출처 : 이것이 컴퓨터 공학이다

 

 

대용량 입출력을 위한 B 트리

자식 노드가 여러개이고, 정렬된 상태를 유지하니까 일반 트리보다 적은 탐색 횟수로 데이터를 찾을 수 있다는 것도 알았다.

 

실제 구체적으로 어떻게 탐색하는지는 곧바로 와닿지 않는데, "동작 방식"을 조금 더 알아보자.

 

B트리는 일반 트리와 다르게, 자식으로 여러개의 노드를 가지는 "다진 탐색 트리"이다.

출처 : 이것이 컴퓨터 공학이다

 

 

각 노드에는 하나 이상의 Key가 오름차순으로 저장되어 있다.

key1 < key2 라면 자식 노드"들" 은 key < 자식 < key2 의 키값들이 들어있다.

즉, 범위를 기준으로 자식들이 정해지는 방식이다.

 

또한 노드가 N개라면 자식의 노드는 N + 1개가 된다.

왜냐고?

key1, key2가 있다고 하면 자식은 [자식1 < key1], [key1 < 자식2 < key2], [key2 < 자식] 이렇게 3개의 범위로 나뉘기 때문!

 

마지막으로 리프노드의 깊이가 모두 같다라는 특징이 있다.(편향되지 않으니까 최악의 경우는 없겠구나)

 

 

 

B트리의 변형 B+트리

오늘날에는 보통 B트리보다는 B트리를 약간 변형한 형태를 많이 쓴다고 한다.

그 중 B+ 트리는 어떻게 변형된 형태일까?

 

• B+ 트리의 실질적인 데이터는 전부 최하위 리프노드에 위치한다.
• 최하위 데이터를 저장하는 리프노드는 연결 리스트 형태를 가짐
  • 부모 노드와 다른 리프들간의 범위 연산에 용이함

 

출처 : 이것이 컴퓨터 공학이다

 

 

 

해시테이블보다 B+트리?

해시 테이블 접근 속도는 O(1)이고 트리는 O(logN)일텐데 왜 B+트리를 주로 사용할까?

 

앞의 B+ 트리 범위 특징과 관련해서 생각해보면 좋을 것 같다.

B+ 트리가 결국 범위 연산에 좋은 구조적 특징을 가지고 있기 때문에, 해시 테이블을 사용하면 부등호를 사용하는 범위 연산에서 매우 비효율적으로 동작하게 된다.

 

결국 탐색, 삽입, 삭제 등 모든 연산에서 O(logN)의 시간복잡도를 가지므로 가장 무난(?)하고 준수하다고 생각된다.

 

 

 

 

 

이정도의 특징이 있군! 아니 어느정도 알고 있었는데 왜 대답 못했냐 나녀석..

일단 이렇게 사용되는 이유를 잘 알아두자!!