데이터의 효율적 검색을 돕는 Index

※ 이 글의 전반적인 내용은 아래의 글을 참조하여 작성하였음

https://d2.naver.com/helloworld/1155

 

Index란?

웹 어플리케이션의 백엔드 성능을 높이기 위해 SQL 튜닝을 사용한다. 

SQL 튜닝이란, SQL이 DBMS의 인덱스를 활용하도록 SQL을 수정하는 것을 말한다.

따라서 인덱스를 이해하는 것이 좋은 SQL문을 작성하는 것과, 어플리케이션의 성능을 향상시키는 데에 중요하다.

 

Index: 데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료 구조

 

인덱스는 Table 내의 1개의 Column, 혹은 여러 개의 column을 이용하여 생성할 수 있다(RDBMS에서 해당 Table의 Primary Key는 자동으로 Index가 생성된다). 

데이터베이스 테이블의 모든 데이터를 요청 시 마다 조회하면 시간이 오래 걸리기 때문에 책에 존재하는 색인처럼, 인덱스를 지정한 데이터를 빠르게 검색할 수 있도록 활용한다.

인덱스는 column의 value와 해당 record가 저장된 주소를 key-value 쌍의 형태로 저장한다.

 

Index는 B-Tree로 구현한다

왼: http://1.bp.blogspot.com/-Djz8SoTFVGI/VKw3tQ7FenI/AAAAAAABlUE/5hHN6zZe_Gg/s1600/btree-6.png, 오: https://d2.naver.com/content/images/2015/06/helloworld-1155-1.png

거의 모든 DBMS는 B-Tree 계열(B-Tree, B+-Tree 등)의 인덱스를 사용한다.

B+-Tree는 B-Tree의 변형으로, 일반적인 B-Tree와 달리 데이터 포인터를 리프 노드에만 저장한다.

리프 노드의 상위 노드인 논 리프 노드는 전형적인 B-Tree로 구성되며, 리프 노드를 빠르게 찾는 역할을 한다.

리프 노드에는 key와, key에 대응하는 데이터의 pointer가 저장되어 있다.

 

https://helloacm.com/wp-content/uploads/2016/04/balanced-tree-or-not.png

일반적인 트리를 이용하여 탐색을 할 때, 트리의 상태가 balanced인지 non-balanced인지에 따라 극명한 시간 복잡도 차이를 보인다. ( best case - O(logN), worst case - O(N) )

하지만 균형 트리라도 데이터의 삽입, 삭제 연산이 빈번히 일어나면 balanced 상태가 깨질 수 있기 때문에 데이터베이스의 특성에 걸맞게 Balanced Tree, 그 중에서도 B+-Tree를 탐색용 자료구조로 활용한다.

(다른 탐색용 자료구조인 Hash는 부등호 연산 SELECT에 적합하지 않고, 다른 Balanced Tree인 Red-Black Tree는 한 노드에 저장할 수 있는 데이터가 하나 뿐이다)

 

Index가 왜 B-Tree를 사용하는 지에 대한 자세한 설명은 아래의 링크에서 확인할 수 있다.

https://helloinyong.tistory.com/296

[2020.10.25] 데이터베이스 인덱스는 왜 'B-Tree'를 선택하였는가

 

Index의 동작 방식과 사용

특정 Column을 Index로 지정하고 나면 초기 table 생성 시 만들어진 [MYD, MYI, FRM] 3개의 파일 중 MYI에 해당 Column을 색인화하여 저장한다.

이후 사용자가 Index를 사용하는 SELECT 쿼리를 수행할 수 해당 Table을 검색하는 것이 아닌 B-Tree로 구성해놓은 MYI 파일의 내용을 검색한다.

만약 Index를 사용하지 않은 SELECT 쿼리라면 해당 Table을 Full Scan하여 모두 검색한다.

 

검색 성능을 위해 Optimizer(옵티마이저)는 입력된 쿼리를 재작성하게 되는데, 이 때 인덱스의 사용을 위해서는 WHERE 절에 Range 조건이 필요하다(없다면 table full scan을 시도한다).

Range 조건은 값의 대소 비교 (크다 > , 작다 < , 크거나 같다 ≥ , 작거나 같다 ≤ , 같다 = )와 같은 비교문으로 기술한다.

인덱스는 값의 대소 비교를 토대로 트리를 구성하기 때문에 대소 비교가 아닌 조건은 B+-Tree를 사용해서 값을 찾을 수 없다(ex. <>, !=, IS NULL 등).

인덱스를 사용하도록 튜닝한 쿼리 - https://d2.naver.com/helloworld/1155

 

두 개 이상의 column을 묶어 인덱스를 만들 때(Multi-Column Index, 복합 인덱스) 에는 column의 순서가 중요한 영향을 끼친다. 복합 인덱스에서는 WHERE 절에 인덱스 키의 첫 번째 column을 사용해야 인덱스 스캔을 수행한다.

 

Index의 활용을 최적화하자

인덱스를 잘 활용하면 데이터베이스 SQL 튜닝 효과를 볼 수 있지만, 인덱스를 많이 만드는 것이 무조건적인 성능 향상으로 이어지는 것은 아니다.

자칫하면 인덱스 관리 비용이 증가하고, INSERT/UPDATE/DELETE의 성능 저하의 원인이 될 수 있다.

Index가 적용된 Column에 INSERT/UPDATE/DELETE 시 발생하는 현상

 

• INSERT : 기존 블록에 여유 공간이 없을 시 일부를 새 블록으로 옮긴 후 기존 블록에 빈 공간을 만들어 새로운 데이터 추가(성능 느려짐)
• DELETE : 데이터가 지워지지 않고, 사용 안 됨 표시만 해둔다 → 실질적으로 삭제되지 않음
• UPDATE : 일반적인 수정이 아닌, DELETE → INSERT가 발생

 

대부분의 DBMS는 페이지 단위로 I/O를 수행하고, 이러한 디스크 I/O는 메모리 액세스에 비해 매우 큰 비용을 소모하기 때문에 질의 성능을 좌우하는 가장 중요한 성능 지표는 I/O를 수행하는 페이지 개수가 된다.

따라서 디스크 I/O를 최소화하고 대부분의 연산을 데이터베이스 버퍼에서 처리할 수 있도록 질의 처리 과정에서 액세스하는 페이지 수를 최소화 하는 것이 SQL 튜닝의 핵심이다.

 

Index 사용 시 고려해야 할 사항

• 인덱스 키의 크기는 가능한 작게 설계한다
• 분포도가 좋은 칼럼(좁은 범위), 기본 키, 조인의 연결 고리가 되는 칼럼을 인덱스로 구성한다.
• 단일 인덱스 여러 개 보다 다중 칼럼 인덱스를 구성한다.
• JOIN 시 자주 사용하는 칼럼으로 인덱스를 구성한다.
• 되도록 동등 비교(=)를 사용한다.
• WHERE 절에서 자주 사용하는 칼럼에 인덱스 추가를 고려한다.
• 과도한 인덱스 생성은 INSERT/UPDATE/DELETE의 성능 저하 원인이 된다.
• 인덱스 스캔이 테이블 순차 스캔보다 항상 빠른 것은 아니다. 보동 선택도(selectivity)가 5~10% 이내인 경우 인덱스 스캔이 더 우수하다.

 

따라서 데이터베이스 튜닝의 핵심은 적절한 수의 인덱스를 생성하고 질의가 해당 인덱스를 활용할 수 있도록 최적화하는 것이다.

이를 위해 DBMS에 구현된 인덱스 구조와 다양한 활용 기법을 이해하고, 질의 패턴과 사용 빈도, I/O 비용, 저장 공간에 대한 비용을 전체적으로 고려해야 한다.

 

참고 자료: 

• https://lalwr.blogspot.com/2016/02/db-index.html
• https://d2.naver.com/helloworld/1155
• https://gyoogle.dev/blog/computer-science/data-base/Index-.html
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#index