[CS] Database 인덱스 (Index)

인덱스 (Index)

• 테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장한다. 
  • 즉, 인덱스는 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
• 예시: 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index 는 책의 색인과 같다.
• 데이터베이스에서도 테이블의 모든 데이터(책의 내용)를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치(책의 페이지 번호)를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
  • 반대로 인덱스를 사용하지 않은 컬럼을 조회할 경우 전체를 탐색하는 Full Scan 을 수행해야 하는데, Full Scan 은 전체를 비교하여 탐색하기 때문에 처리 속도가 떨어진다.
• 인덱스를 활용하면 SELECT 뿐만 아니라 UPDATE 와 DELETE 의 성능도 향상되는데, 이는 해당 연산을 수행하기 위해 먼저 대상을 조회해야 하기 때문이다.

 

인덱스의 장점

• 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
• 전반적인 시스템의 부하를 줄일 수 있다.

인덱스의 단점

• 인덱스를 관리하기 위해 DB 의 약 10%에 해당하는 저장공간이 필요하다.
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
  • DBMS 는 인덱스를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE 가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.
    • INSERT : 새로운 데이터에 대한 인덱스를 추가
    • DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행
    • UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대한 인덱스 추가

 

데이터 수정이 자주 발생하는 속성에 인덱스를 설정하면

• 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.
  • UPDATE 와 DELETE 는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 하였다. 만약 어떤 테이블에 UPDATE 와 DELETE 가 빈번하게 발생된다면 실제 데이터는 10만 건이지만 인덱스는 훨씬 많이 존재하게 되어, SQL 문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.
• 인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해 주는 것도 중요하다. 그러므로 사용되지 않는 인덱스는 바로 제거를 해주어야 한다.

 

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

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

 

인덱스의 자료 구조

1. 해시 테이블 (Hash Table)

• key 와 value 를 한 쌍으로 데이터를 저장하는 자료구조
• key 값을 이용해 고유한 인덱스를 생성하여 그 인덱스에 저장된 값을 꺼내오는 구조이다.
• 해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (key, value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다.
• 해시 테이블의 시간복잡도는 O(1) 이며 매우 빠른 검색을 지원한다.
• 하지만 해시가 등호(=) 연산에만 특화되어있기 때문에, DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적이다.
• 해시 함수는 입력 값이 조금만 달라져도 완전히 다른 해시 값을 생성한다. 그래서 해시 값들은 정렬된 상태가 아니기 때문에, 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색에는 해시 테이블이 적합하지 않다.
  
  • 예시: "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다.
  • 이러한 이유로 데이터베이스의 인덱스에서는 B+Tree 가 일반적으로 사용된다.

 

B+Tree

• DB 의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree 를 개선시킨 자료구조
• 모든 노드에 데이터(value)를 저장했던 B-Tree 와 *다른 특성을 가지고 있다.
  • 다른 특성 : 리프 노드(데이터 노드)만 인덱스와 함께 데이터(value)를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(key, 자식 포인터)만을 갖는다.
• 리프 노드들은 LinkedList 로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
• 데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 B+Tree 의 리프 노드들을 LinkedList 로 연결하여 순차 검색을 용이하게 하는 등 B+Tree 를 인덱스에 맞게 최적화하였다.
• O(log N) 의 시간복잡도를 갖지만, 해시 테이블보다 인덱싱에 더욱 접합한 자료구조이다.

 

장단점

• 리프 노드를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있고, 하나의 노드에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아져 검색 속도가 향상된다.
• Full Scan 을 하는 경우, B+Tree 는 리프 노드에만 데이터가 저장되어 있고, 리프 노드끼리 LinkedList 로 연결되어 있기 때문에 선형 시간(O(n))이 소모된다. 반면 노드를 확인해야 한다.
• 반면 B-Tree 는 최상의 경우 특정 키를 루트 노드에서 찾을 수 있지만, B+Tree 는 반드시 특정 키에 접근하기 위해서 리프 노드까지 가야 한다는 단점이 있다.

---

[Database] 인덱스(index)란?

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정 - 코드 연