[DB] Index란 무엇인가? Index 자료구조와 성능

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

---

💡인덱스는 데이터 베이스 테이블 검색 성능의 속도를 높여주는 자료 구조이다. 

 

인덱스는 테이블 내의 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다.

 

특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.

인덱스를 생성한 후에 쿼리문에 인덱스 생성 컬럼을 WHERE 조건으로 거는 등의 작업을 하면 옵티마이저에서 판단하여 생성된 인덱스를 타고 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져온다. 

 

예를 들자면, 인덱스는 책에 있는 목차와 같다. 원하는 부분을 찾기 위해 목차에 있는 페이지 번호를 보듯, 인덱스도 인덱스에서 내가 원하는 데이터를 먼저 찾고 저장되어 있는 물리적 주소로 찾아간다.

 

또한 인덱스 생성 시 데이터를 오름차순으로 정렬하기 때문에 정렬된 주소체계라고 할 수 있다. 

 

DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나, 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 

 

👉 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 그대신 데이터의 읽기 속도를 높이는 기능이다.

 

인덱스 자료구조

---

B+-Tree 인덱스 알고리즘

B * Tree 인덱스는 대부분의 DBMS 그리고 오라클에서 특히 중점적으로 사용하고 있는 가장 보편적인 인덱스이다. Root(기준) / Branch(중간) / Leaf(말단) Node로 구성되는 계층적 구조를 갖고 있다.

B+-Tree 인덱스는 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다.

Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다.

하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

왜 index 를 생성하는데 b-tree 를 사용하는가?

데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적일 것 같은데? SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. hash table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다.

 

Primary Index vs Secondary Index

---

Primary Index(기본 인덱스)는 주 인덱스로, 인덱스가 레코드와 직접적으로 연결되어 위치를 결정한다.

데이터 블록 안의 행들의 조직과 저장소에 영향을 미치고, 데이터 블록들은 실제 행 데이터를 저장하는 디스크 블록들이다.

Primary Index는 데이터 블록들 안의 행들을 통해 인덱스 키를 정렬한다.

 

Secondary Index는 보조 인덱스로, 레코드의 위치를 결정짓지 않고 그저 레코드의 위치가 어딘지 알려주는 역할을 한다. 위치에 영향을 끼치지 않기 때문에 인덱스에서 명시적으로 언급을 해야지만 레코드의 위치를 알 수 있다.

그렇기 때문에 Secondary Index는 순서를 가지지 않고, 인덱스 블록의 인덱스 키만 정렬돼야 한다.

 

Composite Index

---

컴파짓 인덱스(결합 인덱스)란 인덱스를 생성할 때 두 개 이상의 컬럼을 합쳐서 인덱스를 만드는 것을 의미한다.

 

주로 SQL 문장에서 where 절의 조건 컬럼이 2개 이상 AND로 연결되어 함께 쓰일 때 사용한다.

인덱스에 걸려있는 것 중에서 먼저 걸린 index를 먼저 찾으므로 빈도수가 적은 인덱스를 먼저 거는게 더 좋다.

 

인덱스로 설정하는 필드의 속성이 중요하다. title, author 이 순서로 인덱스를 설정한다면 title 을 search 하는 경우, index 를 생성한 효과를 볼 수 있지만, author 만으로 search 하는 경우, index 를 생성한 것이 소용이 없어진다. 따라서 SELECT 질의를 어떻게 할 것인가가 인덱스를 어떻게 생성할 것인가에 대해 많은 영향을 끼치게 된다.

 

인덱스의 성능과 고려해야할 사항

---

기수성과 선택도를 고려하여 인덱싱해야 한다.

 

기수성

특정 데이터 집합의 유니크한 값의 개수

 

전체 행에 대한 특정 컬럼의 데이터 중복 수치에 대한 정보를 기수성이라고 한다. 중복되는 횟수가 높으면 기수성 값이 낮고, 중복되는 횟수가 낮으면 기수성 값이 높다고 표현한다.

만약 데이터의 중복되는 횟수가 낮은 컬럼을 이용하여 데이터를 그룹 지으면 그룹에 편성되는 데이터의 수가 적어지기 때문에 탐색이 빨라지는 효과를 얻게 된다.

 

선택도

데이터 집합에서 특정 값을 얼마나 잘 선택할 수 있는지에 대한 지표

 

선택도는 기수성으로 계산할 수 있다. 기수성 값이 높을수록 선택도 또한 값이 높아지고, 선택도가 '1'이라는 의미는 모든 값이 유일하다는 의미이다.

높은 선택도를 가지는 컬럼을 인덱스로 설정하는 경우 조회 성능이 향상된다. 

 

 

 

 

 

 

 

참고

 

[DB개념] :: Index Structures (인덱스 구조)

 

DB 인덱스(INDEX) 개념 및 설정 시 고려사항