[DB] Index?

목차 LIST

 

 

Index(인덱스)란?

데이터베이스 분야에서 테이블에 대한 동작의 속도를 높여주는 자료 구조로 테이블의 검색 속도를 향상시켜준다.

 

전공 책에서 궁금한 내용을 찾을 때 제일 뒤 색인을 사용하는데 데이터베이스의 index가 바로 그런 역할을 한다.

 

데이터베이스에서 테이블 검색 시 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 인덱스를 사용한다.

 

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

 

https://coding-factory.tistory.com/746

위 이미지를 보면 인덱스를 사용해서 검색 쿼리를 날리면 Index에 먼저 접근하고, 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 방식으로 검색 속도를 향상시킨다.

 

인덱스에서 원하는 데이터를 찾고 -> 저장되어 있는 물리적 주소로 접근

 

장점

index의 특징은 데이터가 정렬되어있다는 것이다. 이러한 특징 덕분에 조건 검색의 효율을 높여준다.

예를 들면 테이블에 where 조건을 걸면 테이블을 full scan 해서 조건에 해당하는 데이터를 찾는다.

하지만 인덱스 테이블을 사용하면 정렬된 데이터를 사용하기 때문에 더욱 빠르게 데이터를 찾을 수 있다.

 

단점

정렬된 상태를 계속 유지시켜야 한다.

따라서 insert, delete, update가 자주 일어나는 테이블의 경우 작업이 일어날 때마다 Index 테이블의 값을 재정렬해야한다.

또한 Index 테이블에도 작업을 함께 해야한다.

 

주의

검색 쿼리를 날릴 때 무조건 index를 사용하는 것이 항상 더 좋지는 않다.

인덱스는 테이블 전체 데이터 10-15% 이하의 데이터를 처리하는 경우에 효율적이며 그 이상의 데이터를 처리할 때는 사용하지 않는 것이 좋다.

또한 인덱스를 관리하기 위해서는 데이터베이스의 약 10% 정도의 저장 공간이 추가로 필요하다.

Index는 무조건 생성하는 것이 아니라 필요한 경우에 충분한 검토를 하고 사용해야한다.

 

인덱스 자료구조

1. 해시 테이블

• 컬럼 값으로 생성된 해시를 기반으로 한다.
• 시간 복잡도는 O(1)이며 검색이 빠르다.
• 연속적인 데이터를 위한 순차 검색이 불가능하다. (예: 부등호 <,>)

2. B+ Tree

• 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다.
• BTree의 리프노드들을 LinkedList로 연결하여 순차 검색에 용이하다
• 시간복잡도는 O(log_2n)지만 해시테이블보다 흔하게 사용된다.

 

 

B-tree의 핵심: 데이터가 정렬된 상태로 유지되어 있음

 

http://www.btechsmartclass.com/data_structures/b-trees.html

B-tree의 장점은 '모든 값을 같은 시간에 찾을 수 있다' 라는 균일성이다.

위 예시에서 어떤 노드를 찾든 시간 복잡도는 O(logN)이다.

 

이러한 B-tree에도 위기가 있는데.. 테이블에 insert, delete, update 명령이 들어올수록 트리의 균형이 깨진다.

빈도가 높을 수록 인덱스 재구성을 해서 트리의 균형을 찾아야 한다.

 

 

B+tree?

https://zorba91.tistory.com/293

B+tree는 B-tree의 확장개념으로 리프 노드(제일 아래 층)에만 key와 data를 저장하고 리프 노드는 linked list로 연결되어 있다.

 

장점

1. 리프 노드에만 데이터를 담아두기 때문에 메모리를 더 확보할 수 있다.

2. 리프노드에만 데이터가 있기 때문에 한 번의 선형탐색만 하면 돼서 B-tree에 비해 빠르다.
참고로 B-tree는 모든 노드를 확인해야 한다.

 

 

 

References

https://coding-factory.tistory.com/746

https://zorba91.tistory.com/293