B Tree 계열의 알고리즘을 활용한 DB 인덱싱 튜닝

문제 정의

게시판의 데이터가 많아질수록 DB에서 게시판을 불러오는 속도가 느려지는 상황 발생

예상 원인

• Full Table Scan으로 인해 속도가 느려진다.
• 인덱스 미사용으로 인한 비효율적인 검색
• 디스크 I/O 증가

 

기술 선정

기술	설명	장점
Hash Index	특정 값(=)에 대해 해시 테이블을 생성하여 빠르게 검색	'=' 검색 속도가 빠름
Full-Text Index	긴 텍스트(TEXT, VARCHAR)에서 키워드 검색을 빠르게 수행	특정 키워드 검색 최적화
B+ Tree Index	범위 검색(>, <, BETWEEN)을 최적화	특정 범위 검색에 효과적

 

 

B+ Tree 인덱스 선정 이유

기존에 사용하고 있는 MariaDB에서 기존 테이블을 변경하지 않으면서, 범위 검색 성능을 최적화하기 위한 최적의 선택지는 B+ Tree 인덱스라고 생각하여 B+ Tree 기반 인덱스를 활용하여 데이터 조회 속도를 최적화하기로 결정하였다.

• Hash Index : 범위 검색 불가능
• Full-Text Index : 텍스트 검색 전용

 

데이터의 양과 시간 복잡도

DB의 데이터 양이 아주 적으면 인덱스를 사용해서 데이터를 검색하는 것은 테이블을 풀스캔을 하는 것보다 비효율적일 수 있다. 하지만 테이블을 풀스캔하는 것은 무식하지만 직관적이고 명료한 검색 방법인 것에 비해서 인덱스를 활용하는 것은 데이터 검색은 관리할 데이터의 양이 늘어나고 비교적 고차원적인 방법이며, 실무에서는 소량의 데이터가 존재하는 테이블은 거의 없을 것이다라고 생각한다.

따라서 데이터의 양에 따른 검색 속도를 그래프로 보면 아래와 같다. 또한, 굳이 풀 스캔과 비교하지 않더라도, AVL과 같은 Binary Search Tree와 비교해도 훨씬 뛰어난 성능을 보여준다.(동일한 데이터를 더 적은 노드의 Depth로 관리할 수 있고, 그로 인해 특정 데이터를 찾기 위해 하드 디스크에 접근하는 횟수를 줄일 수 있기 때문)

 

적용

BOARD_CREATED_AT에 BTREE 인덱싱을 적용한다.

CREATE INDEX idx_board_created_at ON BOARD(BOARD_CREATED_AT);

적용 전

적용 후

 

결과

• 적용 전: 0.36793900
• 적용 후: 0.10785900

적용 전 보다 적용 후 70.69% 향상된 것을 확인할 수 있다.

 

참고 문헌

https://velog.io/@juhyeon1114/MySQL-Index%EC%9D%98-%EA%B5%AC%EC%A1%B0-B-Tree-BTree