06. 기술면접 - 데이터베이스 - 인덱스 (Index)

공부목적으로 다른 블로그의 글을 그대로 따라치면서 작성되었습니다. 저작권 문제 시, 비공개 처리하겠습니다

인덱스 (Index)

- 인덱스(index)의 원래 뜻은 색인. 데이터베이스에서 조회 및 검색을 더 빠르게 할 수 있는 방법/기술, 혹은 이에 쓰이는
자료구조 자체를 의미하기도 한다

 

https://mangkyu.tistory.com/96

메모리에서 인덱스를 생성하여 파일형태로 저장해놓는다

 

https://mangkyu.tistory.com/96

인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE 나 DELETE 의 성능이 함께 향상된다

그러한 이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다

 

인덱스 관리

DBMS는 index 를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다
그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE 가 수행된다면
각각 다음과 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다

- INSERT : 새로운 데이터에 대한 인덱스를 추가함
- DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
- UPDATE : 기존의 인덱스를 사용하지 않음을 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

- 장점
    1. 테이블을 조회하는 속도와 그에 따른 성능을 향상 시킬 수 있다 (B-Tree 로 탐색하기 때문, 기본은 순차탐색)
    2. 전반적인 시스템의 부하를 줄일 수 있다 (탐색 속도가 빠르기 때문)

- 단점
    1. 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다 (저장하여 관리하기 때문)
    2. 인덱스르 관리하기 위해 추가 작업이 필요하다
    3. 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다
        -> 만약 CREATE, DELETE, UPDATE 가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 
            성능이 오히려 저하되는 역효과가 발생할 수 있다. 그러한 이유 중 하나는 DELETE 와 UPDATE 연산 때문
            UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 하였다. 만약 어떤 테
            이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가
            게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.

인덱스를 활용하면 좋은 경우

- 규모가 작지 않은 테이블
- INSERT, UPDATE, DELETE 가 자주 발생하지 않는 컬럼
- JOIN 이나 WHERE 또는 ORDER BY 에서 자주 사용되는 컬럼
- 데이터 중복도가 낮은 컬럼

인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그렇기 때문에 사용하지 않는 인덱스는 바로 제거를 해주어야 한다. 

사용이유

select 문을 사용하여 원하는 조건의 데이터를 검색할 때, 저장된 데이터의 양이 엄청나게 많다면 검색을 위한 순회에
많은 자원과 시간이 소모될 것 이다. 이 때 도움이 되는게 인덱스이다

자주 조회되는 Column 에 대한 Index Table 을 따로 만들어 SELECT 문이 들어왔을 때 Index 테이블에 있는 값들로
결과 값을 조회해 온다. 그래서 Index 를 잘 사용한다면 "검색" 연산을 실행했을 때 성능을 올릴 수 있게 된다

동작

- Index Table 에서 where 에 포함된 값을 검색

- 해당 값의 table_id PK 를 흭득

- 가져온 table_id PK 값으로 원본 테이블에서 값을 조회

DBMS는 인덱스를 다양한 알고리즘으로 관리를 하고 있는 데 일반적으로 B - Tree (이진 탐색 트리) 알고리즘 사용
(물론 해쉬테이블 자료구조 인덱스도 있다)

 

해쉬 테이블 방식

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

https://mangkyu.tistory.com/96

해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다. 해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

즉, 예를 들면 "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree가 일반적으로 사용된다.

> +추가 B-Tree 를 사용하는 이유 

- hash table 이 더효율적이지 않을 까 라는 생각을 하게 된다
- 하지만 select 질의 조건에는 부등호 연산 (<>) 도 포함되어 있다
- hash table 은 동등한 연산에 특화된 자료구조 이기 때문에 부등호 연산 사용시 문제 발생

const userTable = {
  1: {
    name: 'A'
  },
  
  2: {
    name: 'B'
  }
}

Hash Table 을 이용하여 userTable[1] 처럼 빠르게 접근 가능하지만 1=1 이라는 동등 연산에 빠르다

select * from user where id = 1; // 아이디가 1인 유저 단 건 조회

 

하지만 동등 연산만 사용하지 않기 때문에 부등호 연산까지 포함한다면 B-Tree가 효율적이다

select * from user where id >= 1; // 아이디가 1 이상인 유저들 조회

 

B+Tree 방식

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

Leaf Node=리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
리프노드들은 LinkedList로 연결되어 있다.
데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

이러한 이유로 비록 B+Tree는 O(log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

아래의 그림은 InnoDB에서 사용된 B+Tree의 구조이다.

https://mangkyu.tistory.com/96

InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다.

간단한 구조

 

주의할 점

- 인덱스는 따로 테이블의 형태로 관리가 된다. 자원을 소모한다는 의미.
   때문에 무분별한 인덱스의 사용은 성능에 부정적인 영향을 미칠 수 있다.

-  또한 인덱스는 이진트리를 사용하기 때문에 기본적으로 정렬되어 있다. 이로 인해 검색과 조회의 속도를 향상 시킬 수
   있다.
    - INSERT :  테이블에는 입력 순서대로 저장되지만, 인덱스는 테이블에는 정렬하여 저장하기 때문에 성능 저하 발생
    - DELETE : 테이블에서만 삭제되고 인덱스 테이블에는 남아있어 쿼리 수행 속도 저하
    - UPDATE : 인덱스에는 UPDATE가 없기 때문에 DELETE, INSERT 두 작업 수행하여 부하 발생

- 데이터의 중복이 높은 컬럼(카디널리티가 낮은 컬럼) -> 낮은 컬럼 순으로 인덱싱을 해야 효율적이다

 

참고

https://mangkyu.tistory.com/96

[Database] 인덱스(index)란?