[데이터베이스] 인덱스(Index)

인덱스(Index)

---

인덱스(index) 란 ?

 

인덱스는 데이터베이스 테이블에 대한 검색 속도를 높여주는 자료구조이다. 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아보는 것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 인덱스는 책의 색인과 같다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 즉 데이터베이스 테이블의 컬럼을 색인화 하게 되며 검색 시 해당 테이블의 레코드를 Full scan 하는 것이 아니라 색인화 되어있는 Index 파일을 검색하여 검색 속도를 빠르게 한다. 

 

 

 

---

인덱스(Index)의 원리

 

인덱스를 해당 컬럼에 주게 되면 초기 테이블 생성 시 만들어진 MYD, MYI, FRM 3개의 파일 중에서 MYI에 해당 컬럼을 색인화 하여 저장한다. (인덱스를 사용 안 하는 경우에는 MYI 파일은 비어 있다.)  인덱스를 해당 컬럼에 만들게 되면 해당 컬럼을 따로 인덱싱하여 MYI 파일에 입력한다. 이후에 사용자가 SELECT 쿼리로 인덱스를 사용하는 컬럼을 탐색 시 MYI 파일의 내용을 검색하게 된다.

 

 

 

 

* MYD 

MySQL 데이터 베이스 데이터 파일이며 데이터베이스의 행 내에 저장된 실제 데이터를 포함한다.

MYD 파일은 테이블 형식 데이터가 포함된 해당 .FRM 파일과 데이터베이스 인덱스 역할을 하는 .MYI 파일과 

함께 저장된다. 

 

 

* 정리

인덱싱한 컬럼의 데이터를 물리적 주소와 함께 따로 MYI 파일에 저장해 두면 

테이블 검색 시 데이터를 Full scan 하는 것이 아니라 MYI 파일의 내용을 검색하여  

해당 조건에 맞는 데이터를 빠르게 탐색할 수 있다. 즉 검색 성능을 향상시킬 수 있다. 

인덱스는 특정 컬럼을 기준으로 생성하고 기준이 된 컬럼으로 정렬된 인덱스(Index) 테이블이 생성된다.

즉, 별도의 공간에 특정 컬럼을 인덱싱한 인덱스 테이블을 생성하여 데이터 탐색 시 검색 속도를 높여 효율성을 향상시킨다.

 

 

---

인덱스(Index)의 관리

 

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

 

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

---

인덱스(Index)의 장점과 단점

 

[장점]

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

[단점]

• 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

 

만약 INSERT, DELETE, UPDATE 가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대 해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. DELETE 와 UPDATE 연산 시 기존 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해주게 된다. 인덱스에는 UPDATE 개념이 없기 때문에 테이블에 UPDATE 가 발생할 경우 인덱스에서는 DELETE 가 먼저 발생한 후 INSERT 가 발생하게 된다. 즉 DELETE 와 INSERT 두 개의 작업이 인덱스에 동시에 일어나 다른 DML 보다 더 큰 부하를 주게 된다.

이러한 이유로 UPDATE, DELETE 가 빈번하게 발생된다면 실제 데이터가 10만건이지만 인덱스는 100만건이 넘어가게 되어 SQL 쿼리 문 처리 시 오히려 성능이 떨어지게 된다. 

 

 

* 정리

인덱스를 사용하는 것만큼이나 생성된 인덱스를 관리해주는 것이 중요하다.

그러므로 사용되지 않는 인덱스는 바로 제거를 해주어야 한다. 

 

---

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

 

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

---

인덱스(Index)의 자료구조

 

1. 해시 테이블(Hash Table)

 

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 각각의 Key 값에 해시함수를 적용하여 배열의 고유한 Index 를 생성하고, 이 Index 를 활용하여 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 

 

 

해시 테이블 기반의 DB 인덱스는 (데이터[컬럼의 값], 데이터의 위치) = (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다. 하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 매우 제한적인데 해시가 등호(=) 연산에만 특화 되어있기 때문이다. 해시 함수는 값이 1이라도 달라지는 경우 완전히 다른 해시 값을 생성하는데 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다. 

 

---

2. B+트리(B+tree)

 

 

[이진 트리 vs B-Tree vs B+Tree 😊]

 

1. 이진 트리

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다.

 

 

 

 

2. B-Tree

B 트리라고 부르며, 하나의 노드에 많은 정보를 가질 수 있으며 Balanced Tree의 일종이다. 하나의 노드에 담은 자료의 수가 M개 라면 M차 B-Tree 라고 부르며 이는 자식 노드가 최대 M 개임을 뜻 한다. 하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 효율적으로 저장소에 담을 수 있다. 루트 노드는 적어도 2개 이상의 자식 노드를 가지며, 루트 노드를 제외한 모든 노드는 적어도 M/2 개의 자식 노드를 가진다.

 

 

 

3. B+Tree

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 구조이다.

 

• 리프 노드(데이터 노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(Key)만 갖는다. 
• 리프 노드들은 연결 리스트로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드 크기와 같지 않아도 된다. 
• full scan 을 하는 경우 B+Tree는 leaf node 에만 데이터가 저장되어 있고, leaf node 끼리 LinkedList로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.
•  B-Tree는 가장 빠를 경우 root node에서 찾을 수 있지만, B+Tree 같은 경우 반드시 특정 key에 접근하기 위해서 leaf node 까지 가야한다.

 

해시테이블에서 언급했듯이 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 따라서 B+Tree의 LinkedList 를 이용하면 순차 검색의 효율적으로 할 수 있게 된다.