DB indexing
인덱스(index)란?
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.
데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
인덱스(index)의 장점과 단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. 그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문이다. 앞에서 설명한대로, UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 하였다. 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.
결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다.
Index 자료구조
-
B-Tree 인덱스 알고리즘
일반적으로 사용되는 인데스 알고리즘은 B-Tree 알고리즘이다. B-Tree 인덱스는 칼럼의 값을 변형하지 않고 (사실 값의 앞부분만 잘라서 관리한다.) 원래의 값을 이용해 인덱싱하는 알고리즘이다.
-
Hash 인덱스 알고리즘
칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 등 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.
-
왜 index를 생성하는데 b-tree를 사용하는가?
데이터에 접근하는 시간복잡도가 0(1)인 hash table이 더 효율적일 것 같은데? SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. hash table을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다.
인덱스(index)를 사용하면 좋은 경우
- 규모가 작지 않은 테이블
- INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
- JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
- 데이터의 중복도가 낮은 컬럼
- 기타 등등
인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그렇기 때문에 사용하지 않는 인덱스는 바로 제거를 해주어야 한다.
Index 의 성능과 고려해야할 사항
SELECT 쿼리의 성능을 월등히 향상시키는 index는 항상 좋은 것일까? 결론부터 말하자면 그렇지 않다.
우선 첫째, index를 생성하게 되면 insert,delete,update 쿼리문을 실행할 떄 별도의 과정이 추가적으로 발생한다. insert의 경우 index에 대한 데이터도 추가해야하므로 그만큼 성능에 손실이 따른다. delete의 경우 index에 존재하는 값은 삭제하지 않고 사용 않는다는 표시로 남게 된다. 즉 row의 수는 그대로인 것이다. 이 작업이 반복되면 어떻게 될까?
실제 데이터는 10만건인데 데이터가 100만건 있는 결과를 낳을 수도 있는 것이다. 이렇게 되면 인덱스는 더 이상 제 역할을 못하게 되는 것이다. update의 경우 insert의 경우, delete의 경우의 문제점을 동시에 수반한다. 이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 때문이다. 즉 변경 전 데이터는 삭제되지 않고 insert로 인한 split도 발생하게 된다.
DATABASE가 index를 찾아가는 검색 데이터 구조
DB가 인덱스를 찾아갈 때 일반적으로 이진트리(binary search), 이진 탐색을 사용합니다. 대량의 데이터를 검색할 떄 유용합니다. 인덱스가 지정되지 않은 데이터는 풀 테이블 스캔(full table scan)방식을 사용합니다.
이진 탐색이 어떤 것인지 예시로 설명드리겠습니다. 1~100개 인덱스가 있는 자료에서 70번째 데이터를 찾을 때 1부터 100까지 차례로 찾으면 오래 걸릴 것입니다. 하지만 DB는 먼저 100의 반인 50을 검사합니다. 50 이상,이하인지 검사 후 70은 50 이상이니 50~100까지 검사합니다. 그 후 그 절반인 75를 검사해 또 이상,이하 판별을 합니다. 그렇게 계속해서 절반씩 찾아가며 원하는 값에 금방 근접할 수 있습니다.
이진탐색은 굉장히 효율적인 방법이지만 이 방법을 사용하기 위해서는 전제조건이 있습니다. 인덱스가 미리 정렬 되어 있어야합니다. 인덱스로 검색을 안하더라고 검색하고자 하는 데이터가 미리 정렬되어 있어서 이진탐색을 할 수 있다는 점이 있습니다.
