[DB] 인덱스 (Index)

인덱스는 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다.

테이블의 특정 컬럼(속성)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후에 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장한다.

컬럼의 값과 물리적 주소를 해시맵처럼 key, value 한 쌍으로 관리한다.

 

쉽게 말해서 책에서 원하는 내용의 글을 찾을 수 있도록 도와주는 책갈피와 같은 역할이라고 보면 될 것 같다.

• 데이터 - 책의 내용
• 인덱스 - 책의 목차
• 물리적 주소 - 책의 페이지 번호

 

 

인덱스 장점 / 단점

인덱스 장점

1. DB 데이터 검색 속도 및 성능 향상.
2. 인덱스에 의한 정렬된 형태를 갖는 데이터.
   • 특정 조건의 데이터를 찾기 위해서는 Full Scan을 통해 전체적인 데이터 전부를 조건과 비교하여 찾았어야 했으나, 인덱스를 사용하면 데이터들이 정렬된 상태로 별도의 메모리에 따로 저장이 되어있기 때문에 조건에 맞는 데이터를 빠르게 조회 가능하다.

 

인덱스 단점

1. 인덱스를 저장하기 위한 별도의 추가 저장 공간 필요
2. 인덱스를 사용하기 위한 추가 작업 필요
   • 인덱스는 가능하다면 수정/삭제/삽입과 같은 작업이 거의 없는 컬럼에 대해 적용하는 것이 좋다. 만약 해당 작업들을 수행하려면 삽입 시에는 새로운 데이터에 대한 인덱스를 추가해야하고, 삭제 시에는 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 수행해야 하며, 수정 작업의 경우에는 기존의 인덱스를 사용하지 않음 처리를 진행해야한다. 또한 갱신된 데이터에 대한 인덱스 추가도 해주어야 한다.
   • 삭제나 수정 시에 기존의 데이터에 대한 인덱스를 없애는 것이 아니라 사용하지 않음 처리를 진행하는 것이므로 계속해서 존재는 한다. 따라서 계속해서 해당 작업들을 진행하게 된다면 인덱스가 과도하게 커지게 된다.
3. 무지성으로 사용하면 오히려 검색 성능 저하
   • 예를 들어 나이, 성별과 같은 값의 범위가 적은 컬럼의 경우에는 인덱스를 적용하게 되면 인덱스를 읽고 나서 다시 많은 데이터를 조회해야 하기 때문에 비효율적이다.

 

 

효율적인 인덱스 사용처

데이터의 값 범위가 넓고 중복이 적을수록, 조회가 많거나 정렬된 상태가 유용한 컬럼, 수정/삭제/삽입 작업이 빈번하지 않은 컬럼에 사용하는 것이 좋다.

• 규모 혹은 크기가 테이블
• 삽입 / 삭제 / 수정 작업이 빈번하지 않은 컬럼
• where 문과 같은 조건문이 자주 사용되는 컬럼
• 데이터의 중복이 없는 컬럼

 

 

 

인덱스 자료구조

인덱스는 여러 자료구조를 이용해서 구현할 수 있다.

대표적으로 해시 테이블, B+Tree 구조가 있다.

 

 

(1) 해시 테이블 (Hash Table)

해시 테이블은 인덱스와 유사하게 key, value 한 쌍으로 데이터를 저장하는 자료구조이다.

key값을 이용해 value 값을 구한다.

시간복잡도는 평균적으로 O(1) 이며, 매우 빠르게 데이터를 찾아낼 수 있다.

 

 

(2) B+Tree

기존의 B-Tree는 특정 데이터에 대한 검색은 효율적이지만, 트리의 모든 노드를 전부 다 조회해야 하는 비효율적인 문제가 있다.

B+Tree 는 이러한 문제를 보완한 자료구조이다.

 

B+Tree는 오직 leaf node(마지막 자식 노드)에만 데이터를 저장하고, 그 이외의 노드들에는 자식을 가리키는 포인터만이 존재한다.

B+Tree는 leaf node 끼리는 linked list로 연결되어있다.

따라서, 노드 앞서 말한 B-Tree의 단점이 모든 노드 전체 조회를 이행할 필요가 없다.

 

 

위의 사진에 보이는 것처럼 leaf node 에서 key를 올바르게 찾기 위해서 key가 중복될 수가 있다.

즉 예를 들자면, leaf node에 7, 14번 key값이 존재하는데, 11번 key값을 찾기 위해서 중간 노드에 존재했던 key값인 9번을 leaf node에서 중복으로 사용한 것이다.

 

 

B+Tree 장점

1. leaf node에만 데이터를 저장하기 때문에 메모리를 더 확보할 수 있다. 쓸데없는 일로 GC가 발동될 일도 없을 것이다. 
2. 1번으로 인한 특성 덕분에 상위 노드에는 자식을 가리키는 포인터가 존재할 수 있는데, 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 깊이가 낮아지고 이로써 검색 속도 또한 많이 향상되게 되는 것이다.
3. Full Scan을 진행하게 된다면, B-Tree 의 경우에는 모든 node들을 조회함으로써 시간이 많이 소요될 것이다. 하지만 B+Tree는 각 leaf node들끼리 linked list로 이어져있기 때문에 시간 소요가 적다.
4. 인덱스를 생성한 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 이 떄 B+Tree의 leaf node에 적용된 linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 된다.

 

B+Tree 단점

1. 앞서 B+Tree는 leaf node에 데이터가 존재한다고 하였는데, 따라서 원하는 key값의 데이터를 얻기 위해서는 leaf node까지 내려가야 된다는 것이다.

 

 

 

인덱스 SQL언어에서의 사용법 및 적용법 추가 정리 !!!!!!!!!

 

 

 

[참고]

https://rebro.kr/167 

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