[SQL] 인덱스의 내부 작동 원리와 구조

인덱스의 내부

클러스터형 인덱스와 보조 인덱스 모두 균형 트리 구조로 되어있다.

 

 

균형 트리란?

나무를 뒤집어 놓은 모양처럼 생긴 자료구조이다.

 

노드(node): 균형 트리에서 데이터가 저장되는 공간을 말한다.

루트 노드(root node): 가장 상위에 있는 노드를 말한다. 모든 출발은 이 루트 노드에서 시작된다.

리프 노드(leaf node): 제일 마지막에 있는 노드를 말한다. 

중간 노드(internal node): 루트 노드와 리프 노드 사이에 있는 노드들을 말한다.

 

MySQL에서는 노드를 페이지(page)라고 부르므로 페이지라는 용어를 사용하겠다.

 

 

균형 트리 작동 예시

각 페이지에는 여러 개의 데이터가 저장될 수 있다.

예를 들어, 3개의 독립된 페이지가 있다고 가정하자. 즉 3개의 리프 페이지만 존재하는 상태이다.

여기서 3번째 페이지에 있는 데이터 K를 검색하기 위해선 모든 페이지를 다 검색하는 전체 테이블 검색(Full Table Scan)을 해야한다. 최악의 경우 모든 데이터를 다 검색해야 원하는 데이터 K를 가져오는 것이다.

 

 

위에서 인덱스가 되어 있지 않는 상태를 이야기했다.

그럼 인덱스를 사용해, 다시 말해 균형 트리를 사용해 데이터를 검색하는 경우를 살펴보자.

 

리프 페이지 3개가 있는 상황에서 루트 페이지 1개를 추가해보자.

루트 페이지에는 리프 페이지 데이터의 첫번째 데이터들만 가지고 있다.

원하는 데이터 K를 찾기 위해 루트 페이지의 데이터를 비교하고 K가 어떤 리프 페이지에 있는지 확인한다.

그리고 K가 있는 리프 페이지로 접근해 K를 찾아낸다.

 

 

루트 페이지가 있으면 없을 때보다 조회하는 페이지 수가 줄어든다는 것을 알 수 있다.

이처럼 인덱스는 검색 결과에는 영향이 없지만 검색 속도를 높여주는 역할을 한다.

 

 

균형 트리의 페이지 분할

균형 트리가 어떻게 검색 속도를 향상시켜주는지 확인해봤다.

그럼 데이터 삽입, 수정, 삭제의 경우는 어떠할까?

일반적으로 인덱스는 조회 이외의 기능에 대해선 성능이 오히려 나빠진다.

 

루트 페이지 1개, 리프 페이지 3개의 구조에서 데이터 삽입을 진행해보자.

데이터를 계속 삽입하다보니 2번째 페이지의 저장 공간이 남지 않았고 새로운 데이터를 2번째 페이지에 넣어야한다.

그럼 이제 2번째 페이지를 2개의 페이지로 분할을 해야한다.

새로운 페이지를 만들고 2번째 페이지의 데이터를 균등하게 나눠 저장해야한다.

 

만약 중간 노드에서 페이지 분할이 일어난 다면 모든 하위 페이지의 구조를 변경해야하는 상황이 올 수도 있다.

설상가상으로 중간 페이지가 늘어나면서 루트 페이지의 저장 공간이 부족해지면 루트 페이지도 분할해야한다.

하지만 루트 페이지는 1개여야하기 때문에 새로운 루트 페이지를 만들고 기존의 페이지는 중간 페이지가 된다.

이처럼 균형 트리는 하나의 데이터를 삽입하는데 많은 작업이 소요되기도 한다.