Index

Index란?

인덱스는 말 그대로 책에서의 색인이라고 할 수 있다. 이 비유대로 설명하면 데이터는 책의 내용이고, 인덱스는 데이터가 저장된 레코드의 주소가 된다. 만약 DBMS가 원하는 데이터를 가져오기 위해 데이터베이스 테이블의 모든 데이터를 조회하게 된다면 오랜 시간이 걸릴 것이다. 인덱스는 컬럼의 값과 저장된 주소를 쌍으로 하여 검색의 성능을 높여준다. (인덱스를 통해 바로 검색할 수 있다.)

Index 자료구조

DBMS가 인덱스를 어떤 자료구조로 관리하고 있는지 알아보자.

B+-Tree 인덱스 알고리즘

일반적으로 인덱스를 구현하고 있는 알고리즘이다.

B-Tree

트리 구조는 데이터베이스뿐만 아니라 시스템의 다양한 부분에서 데이터를 유지하기 위해 많이 사용하는 구조이다. 탐색에 대한 소요 시간이 적다는 장점이 그 이유이다.

B-Tree의 핵심은 데이터가 정렬된 상태로 유지되는 것이다. 이를 Binary Search Tree와 같다고 느낄 수도 있지만 B-Tree의 경우 한 노드가 2개 이상의 자식을 가질 수 있기 때문에 이 부분에서 다르다고 할 수 있다.

B-Tree가 빠른 이유

B-Tree의 장점으로 '어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다.'를 꼽을 수 있다. 전체를 모두 조회해야 하는 선형 탐색 대신에 트리 구조를 통해 모든 데이터에 비슷한 시간 내에 접근할 수 있다.

균형트리

B-Tree는 생성 당시에 균형 트리로 구성된다. 균형 트리는 루트에서 리프가지의 거리가 일정한 트리 구조를 의미한다. 그러나 데이터의 삽입, 수정, 삭제와 같은 과정이 반복되면 서서히 균형이 깨지게 된다. 이럴 경우 인덱스를 재구성하여 트리의 균형을 잡아줘야 한다.

B+Tree

B+Tree는 B-Tree의 확장 개념이다. B-Tree의 경우 internal(branch, 중간) 노드에 key와 data를 담을 수 있다. 하지만 B+Tree의 경우 branch 노드에 key만 담아둔다. 리프 노드에서만 key와 data를 저장하고 리프 노드끼리 연결 리스트로 연결되어 있다.

B+Tree 장점

• 리프 노드를 제외한 나머지 노드에는 data가 저장되지 않기 때문에 메모리를 더 확보하여 더 많은 key를 담아둘 수 있게 된다. 하나의 노드에 여러개의 key가 수용되어 Tree의 높이가 낮아진다. 이는 Cache Hit를 높여준다.
• 풀 스캔 시 B+Tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형 탐색으로 가능하다. B-Tree의 경우에는 모든 노드를 확인해 주어야 하기 때문에 B+Tree보다 느리다.

Hash 인덱스 알고리즘

컬럼 값으로 해시 값을 계산하여 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 그러나 값을 변형하여 인덱싱하기 때문에, 특정 문자로 시작하는 값을 검색하는 전방 일치와 같이 값의 일부를 통한 검색이 불가능하다. Hash 인덱스 알고리즘은 주로 메모리 기반의 데이터베이스에서 사용된다.

B-Tree를 사용하는 이유

데이터에 접근하는 시간은 Hash 인덱스 알고리즘이 더 빠르다. 그러나 SELECT 절의 경우 부등호 연산을 통해 검색을 하기도 한다. Hash 테이블은 등호(=)연산으로만 검색이 가능하기 때문에 적절하지 않다.

Primary Index (Clustered Index) vs Secondary Index (Non Clustred Index)

클러스터란 여러 개를 하나로 묶는다는 의미로 사용된다. 클러스터드 인덱스도 이와 마찬가지로 비슷한 것들을 묶어서 저장하는 형태로 구성된다. 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 여기서 비슷한 값들은 물리적으로도 인접한 위치에 저장되어 있는 데이터들을 의미한다.

클러스터드 인덱스는 테이블의 프라이머리 키에만 적용된다. 이는 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 것이다. 클러스터드 인덱스에서는 프라이머리 키 값에 의해 레코드의 저장 위치가 결정되고, 이 때문에 프라이머리 키 값이 변경되면 레코드의 저장 위치 또한 변경된다. 이러한 이유로 프라이머리 키를 신중하게 결정하고 클러스터드 인덱스를 사용해야 한다.

클러스터드 인덱스는 프라이머리 키에 대해서만 적용되기 때문에 테이블 당 하나만 생성 가능하다. 반대로 non 클러스터드 인덱스는 하나의 테이블에 여러개를 생성할 수 있다.

Primary Index(Clustered Index)

• InnoDB 엔진에서 table의 Primary key를 정의하면 Clustered Index가 된다.
• 테이블 당 하나만 가질 수 있다.
• 삽입 시 데이터가 정렬되고 인덱스는 데이터 블록의 첫번째 레코드 주소값을 갖는다. 인덱스가 곧 바로 데이터 블록에 접근하기 때문에 Secondary Index보다 동작이 빠르다.
• 데이터가 정렬되어 저장되기 때문에 Secondary Index에 비해 범위로 질의하는 데에 유리하다. (I/O가 덜 발생되기 때문)

Secondary Index(Non Clustred Index)

• Primary key 이외에 필요한 정렬 기준이 있을 경우 사용한다.
• 하나의 테이블에 여러개를 가질 수 있다.
• 데이터 레코드가 정렬되어 있지 않다.
• 인덱스가 데이터 레코드의 모든 주소값을 가지고 있어야 한다.
• unique하지 않아도 된다.
• 데이터 레코드가 인덱스 순서대로 정렬되어 있지 않기 때문에 범위 조건으로 검색하게 될 경우 많은 I/O가 발생할 수 있다. (성능 저하)
• 인덱스는 모든 레코드에 대한 색인 데이터를 들고 있어야 하고 정렬된다. 때문에 삽입, 삭제, 수정 시 오래 걸릴 수 있고 Primary Index에 비해 많은 공간을 차지한다.

Composite Index(결합 인덱스)

결합 인덱스란 인덱스 생성 시 두개 이상의 컬럼을 합쳐 인덱스를 만드는 것을 의미한다. 보통 WHERE절에서 AND를 통해 조건 컬럼을 2개 이상 연결하여 사용하는 경우에 결합 인덱스를 생성하면 성능이 매우 좋아진다. 만약 이름, 성별 이 순서로 결합 인덱스를 둔 경우 이름으로만 검색하게 되면 성능이 좋지만 성별로만 검색하게 되면 인덱스를 생성한 것이 소용이 없어진다. 따라서 SQL문을 어떻게 작성할 것인지, 어떤 컬럼을 조건으로 더 이용할 것인지를 판단하여 생성해야 한다.

Index의 성능과 고려사항

인덱스는 SELECT 쿼리의 성능을 향상시킨다. 이 문장만 본다면 모든 컬럼에 인덱스를 생성해두면 좋지 않을까라는 생각을 하게 된다. 그러나 모든 컬럼에 인덱스를 두게 되면 다른 부가적인 문제가 생기게 된다.

• 인덱스를 생성하면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때에 별도의 추가적인 과정이 발생한다.
  -> INSERT: 인덱스에 대한 데이터 추가
  -> DELETE: 인덱스에 존재하는 값은 삭제하지 않고 사용하지 않는다는 표시를 남겨 결국에는 안쓰는 공간이 더 많아짐 (DELETE를 아무리 해도 row 수는 그대로)
  -> UPDATE: INSERT, DELETE의 문제점을 동시에 수반. 이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 때문에 변경 전 데이터는 삭제되지 않고 INSERT로 인한 split발생
• 컬럼을 이루고 있는 데이터의 형식에 따라 인덱스의 성능이 악영향을 미칠 수 있다. (어떤 데이터 형식은 인덱스가 효율적이지만 어떤 데이터 형식은 인덱스가 비효율적임)
  -> 이름, 나이, 성별 이렇게 세가지 필드를 가지는 테이블의 경우 이름을 제외한 나머지는 인덱스로 두었을 때에 비효율적임.
  -> 나이, 성별은 값의 범위가 적기 때문에 디스크 I/O가 자주 발생