[MySQL] 13. 인덱스의 내부 작동 원리와 구조, 인덱스에서 데이터 검색하기

클러스터형 인덱스와 보조 인덱스는 모두 내부적으로 균형 트리로 만들어진다. 균형 트리(Balanced Tree)는 '자료 구조'에 나오는 범용적으로 사용되는 데이터의 구조로써 데이터를 검색하는 데 효율적으로 이루어져있다.

 

균형 트리는 나무를 거꾸로 표현한 자료 구조로, 트리에서 제일 상단의 뿌리를 루트, 줄기를 중간, 끝에 달린 잎을 리프라고 부른다.

 

균형 트리

 

 

균형 트리 구조에서 데이터가 저장되는 공간을 노드(Node)라고 한다. 루트 노드(Root Node)는 노드의 가장 상위 노드를 말한다. 모든 출발은 루트 노드에서 시작된다. 리프 노드(Leaf Node)는 제일 마지막에 존재하는 노드를 말한다. 루트 노드와 리프 노드 사이에 있는 노드를 중간 노드(Internal Node)라고 한다.

 

 

 

노드라는 용어는 개념적인 설명에서 주로 나오는 용어이며, MySQL에서는 페이지(Page)라고 부른다.

---

인덱스는 균형 트리로 이루어져 있기 때문에 SELECT의 속도를 향상시킬 수 있다. 다만 인덱스를 구성하면 데이터 변경 작업(INSERT, UPDATE DELETE) 시 성능이 나빠진다. 특히 INSERT 작업이 일어날 때 더 느리게 입력될 수 있다.

 

이유는 페이지 분할이라는 작업이 발생하기 때문인데, 페이지 분할이란 새로운 페이지를 준비해서 데이터를 나누는 작업을 말한다. 페이지 분할이 일어나면 MySQL이 느려지고, 너무 자주 일어나게되면 성능에 큰 영향을 미친다.

 

INSERT 문으로 인한 페이지 분할

 

 

페이지 분할로 인한 중간 노드의 생성