[DB] 인덱스(Index)란

인덱스(Index)란 무엇인가?

인덱스는 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터 베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 인덱스라는 말 그대로 책의 맨 처음 또는 맨 마지막에 있는 색인이라고 할 수 있다. 이 비유를 그대로 가져와서 인덱스를 살펴본다면 데이터는 책의 내용이고 데이터가 저장된 레코드의 주소는 인덱스 목록에 있는 페이지 번호가 될 것이다. DBMS 도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져 오려면 시간이 오래 걸린다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것이다.

//spring 이라는 이름을 업데이트 해주기 위해서는 spring을 먼저 조회해야 한다. 
UPDATE USER SET NAME = 'springboot' WHERE NAME = 'spring'

DBMS 의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다. SELECT 쿼리 문장의 WHERE 조건절에서 사용되는 칼럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져서 오히려 역효과만 불러올 수 있다.

만약 index 를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan 을 수행해야 한다. 이는 모든 데이터를 탐색하는 것인데 당연히 처리 속도가 현저히 떨어진다.

Index 자료구조

그렇다면 DBMS 는 인덱스를 어떻게 관리하고 있는가

B+Tree 인덱스 알고리즘

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조 이다. B+Tree는 모든 노드에 데이터를 저장했던 BTree 와 다른 특성을 가지고 있다.

데이터베이스의 인덱스컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스의 맞게 최적화하였다.

Hash Table 인덱스 알고리즘

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB 인덱스는 매우 빠른 검색을 지원하지만, 해시는 등호(=) 연산에 대해서만 특화되어있고 값이 1이라도 달라지면 완전히 다른 해시 값을 생성한다. 이러한 특성때문에 부등호 연산 (>,<)이 자주 사용되는 데이터베이스 검색을 위해서는 해시테이블이 적합하지 않다. 이런 경우에는 B+Tree 가 일반적으로 사용된다.

Index 의 성능과 고려해야할 사항

SELECT 쿼리의 성능을 월등히 향상시키는 INDEX 항상 좋은 것일까? 쿼리문의 성능을 향상 시킨다는데, 모든 컬럼에 INDEX 를 생성해두면 빨라지지 않을까? 결론부터 말하자면 그렇지 않다. 우선, 첫번째 이유는 INDEX 를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생한다. INSERT 의 경우 INDEX 에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따른다. DELETE 의 경우 INDEX 에 존재하는 값은 삭제하지 않고 사용 안한다는 표시로 남게 된다. 즉 row 의 수는 그대로인 것이다. 이 작업이 반복되면 어떻게 될까?

실제 데이터는 10만건인데 데이터가 100만건 있는 결과를 낳을 수도 있는 것이다. 이렇게 되면 인덱스는 더 이상 제 역할을 못하게 되는 것이다. UPDATE 의 경우는 INSERT의 경우, DELECTE 의 경우의 문제점을 동시에 수반한다. 이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 떄문이다. 즉 변경 전 데이터는 삭제되지 않고 insert 로 인한 split 도 발생하게 된다.

하지만 더 중요한 것은 컬러믕 이루고 있는 데이터의 형식에 따라서 인덱스의 성능이 악영향을 미칠 수 있다는 것이다. 즉, 데이터의 형식에 따라 인덱스를 만들면 효율적이고 만들면 비효율적은 데이터의 형식이 존재한다는 것이다. 어떤 경우에 그럴까?