[SQL] 인덱스의 내부 작동 정리

인덱스의 내부 구조는 어떻게 되어 있나요?

인덱스는 균형 트리(Balanced Tree, B-tree)로 구성되어 있습니다. '자료 구조'에 나오는 범용적으로 사용되는 데이터의 구조입니다.

 

B-tree의 구성은 아래와 같습니다.

• 최상단: 뿌리(Root)
• 중단: 줄기(Internal)
• 최하단: 잎(Leaf)

균형 트리(B-tree) 구조에서 노드는 데이터가 저장되는 공간입니다. 루트 노드, 중간 노드, 리프 노드로 구성되어 있습니다.

MySQL에서는 노드를 페이지(Page)라고 부릅니다. 페이지는 MySQL에서 최소 저장단위이며 1개의 페이지 마다 16KB의 크기를 가집니다.

 

균형 트리 덕분에 데이터베이스에서 빠르게 데이터를 검색할 수 있습니다. 만약 루트와 줄기가 없고 오직 리프 노드만 있다면 데이터를 검색 할 때 처음부터 끝까지 검색하는 전체 테이블 검색(Full Table Scan)을 해야할 것입니다.

 

균형 트리의 페이지 분할이란 무슨 뜻인가요?

인덱스를 구성하는 데이터가 INSERT, UPDATE, DELETE로 데이터가 변경될 수 있습니다. 그럴 경우 성능이 나빠집니다. 왜냐하면 페이지 분할 때문입니다. 페이지 분할은 새로운 페이지를 준비해서 데이터를 나누는 작업입니다.

 

데이터가 삽입될경우 루트 페이지에 새로운 데이터가 입력되고 리프 페이지 혹은 중간 페이지의 개수를 1개 증가시킵니다.

 

클러스터형 인덱스의 구조는 어떻게 되어 있나요?

클러스터형 인덱스(PK)는 자동으로 정렬되어 있으며 루트 페이지, 중간 페이지, 리프 페이지로 구성되어 있습니다.

사전의 철자 순서처럼 기록되어 있습니다.

보조 인덱스의 구조는 어떻게 되어 있나요?

보조 인덱스(UNIQUE)는 정렬 되어 있지 않으나 데이터의 위치는 페이지 번호와 #위치로 기록되어 있습니다. 

책 제일 뒷장의 바로가기 페이지처럼 기록되어 있습니다.

 

인덱스 검색(Index Scan)

인덱스 검색(Index Scan)은 클러스터형 인덱스(PK) 혹은 보조 인덱스(UNIQUE)로 데이터를 검색합니다. 둘 다 빠른 속도를 보이나 클러스터형 인덱스가 더 빠릅니다.