백엔드 개발자의 입장에서 생각 했을 때, 서버의 속도나 성능 개선이 필요할 때 먼저 해볼 수 있는게 무엇이 있을까 생각했다.
기본적으로 서버에서는 DB에서 데이터를 받아와 처리하는 부분이 굉장히 많기 때문에 일단은 먼저 DB의 성능을 개선할 방법을 찾던 중에 '인덱스'라는 것을
알아보기로 했다.
인덱스(Index)란?
먼저 인덱스란 무엇인가부터 알아보자.
인덱스란 우리가 책을 읽을 때 원하는 내용을 찾기 위해 책의 맨 앞, 또는 맨 뒤에 있는 색인 부분을 확인하는데 DB의 인덱스도 이와 비슷하다.
DB 내에 추가적인 공간을 활용하여 기존 PK값이 아닌 다른 Coulm의 값으로 정렬된 자료구조를 만들고 해당 Coulm 값에 대응하는 값으로 기존 튜플의 주소값을 가지게끔 한다.
이렇게 만들어 사용할 경우 데이터를 조회하는 SELECT 뿐만 아니라 UPDATE, DELETE의 성능도 함께 개선 가능하다.
(수정이나 삭제 같은 작업을 수행하기 위해서는 먼저 대상을 조회해야 하기 때문에)
인덱스를 사용하지 않은 Colum을 조회할 경우에는 전체를 탐색하는 Full Scan을 수행해야한다.
DBMS는 인덱스를 항상 최신의 정렬된 상태로 관리해야 원하는 값을 빠르게 탐색 가능하다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행되면 각 연산마다 아래와 같은 추가적인 연산을 해주어야하고 그에 따른 오버헤드가 발생한다.
- INSERT - 새로운 데이터에 대한 인덱스 추가
- DELETE - 삭제한 데이터의 인덱스를 사용하지 않는다는 작업 진행
- UPDATE - 기존의 인덱스를 사용하지 않음 처리하고 갱신된 데이터에 대한 인덱스 추가
인덱스의 장점과 단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능 향상 가능
- 전반적인 시스템 부하 감소
단점
- 인덱스를 관리하기 위해서는 DB의 약 10% 정도의 저장 공간이 필요 -> 무분별하게 사용할 경우 DB 자체의 크기가 커질 수 있음
- 인덱스를 관리하기 위한 추가 작업 필요 (위에서 설명한 것과 같은 추가적인 연산 작업)
- 인덱스를 잘못(무분별하게) 사용할 경우 오히려 성능이 저하 될 수 있음 -> UPDATE와 DELETE는 기존 인덱스 데이터에 대해서 삭제하는 것이 아닌 사용하지 않음 처리를 하기 때문에 실제 데이터는 1000건이라도 인덱스는 그 이상이 될 수 있기 때문이다.
인덱스를 사용하기 좋은 경우
- 규모가 작지 않은 테이블
- INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
- JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
- 데이터의 중복도가 낮은 컬럼
인덱스의 자료구조
인덱스를 구현하는 다양한 자료구조 중에 가장 대표적인 해시 테이블과 B+Tree에 대해서 정리해보자.
해시 테이블
해시 테이블은 [Key, Value] 형태로 데이터를 저장하는 자료구조 중 하나로 빠른 검색이 필요할 때 유용하다. 간단하게 설명하자면 키 값을 해싱한 값을 주소로 사용하기 때문이다. 주의할 점은 해당 주소값이 고유하지 않을 수 있다는 점이다. 다시 본론으로 돌아가서 해시 테이블은 키 값만 입력하면 바로 해당 밸류 값을 찾을 수 있기 때문에 시간복잡도가 O(1)이기 때문에 굉장히 빠른 검색 속도를 가진다.
하지만 DB 인덱스에서는 해시 테이블이 제한적으로 사용되는데 그 이유는 해시가 등호 연사에만 특화되어 있기 때문이다. 부등호 연산이 빈번히 사용되는 DB 검색을 위해서는 해시 테이블이 적합하지 않다.
B+Tree
B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 BTree를 개선한 자료구조이다. 구조는 Root Node/ Branch Node / Leaf Node로 구성되어 있다. B+Tree는 BTree와는 다른 특성들을 가지고 있다.
- 리프 노드만 인덱스와 데이터를 가지고 있고 나머지 노드들은 데이터를 위한 인덱스만을 갖는다.
- 리프 노드들은 LinkedList로 연결되어 있다.
- 데이터 노드의 크기는 인덱스 노드의 크기와 같지 않아도 된다.
Root Node에서 경로를 확인 후에 그에 맞는 Node들로 이동하여 최종적으로 원하는 데이터가 있는 Leaf Node로 도달하게 된다.
Database의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생 될 수 있기 때문에 BTree의 리프 노드들을 LinkedList 형태로 연결하여 순차 검색을 용이하게 하는 등 인덱스의 맞게 최적화하였다.
결론적으로 현재 DB의 인덱스에서는 B+Tree가 일반적으로 사용되고 있다.
참고자료
