DB - Index

DB - Index

---

Index를 사용하는 이유

• 일반적인 테이블에서 데이터의 레코드는 내부적으로 아무런 순서 없이 저장된다. 이때 저장되는 데이터 영역을 Heap영역 이라고 한다. Heap에서는 인덱스가 없는 테이블의 데이터를 찾을 때 무조건 전체 데이터 페이지의 처음 레코드부터 끝 페이지의 마지막 레코드까지 다 읽어서(Full scan) 검색 조건과 비교한다. 그러므로 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것이다.

• 즉 인덱스는 데이터를 select 할때 빨리 찾기 위해 사용된다. 

 

Index란?

• 테이블에 저장된 데이터를 빠르게 조회하기 위한 데이터 객체이다.
• index를 걸면 index를 거는 컬럼을 기준으로 새로운 객체를 생성하여 별도의 디스크 공간에 저장한다.

 

Index의 자료구조

1. B+tree
   • 항상 좌, 우 자식 노드 개수의 밸런스를 유지하므로 최악의 경우에도 무조건 탐색 시간이 O(logn)이 된다.
   • 이진 트리를 확장해서 노드 하나에 여러 데이터가 저장될 수 있다.
   • 각 노드 내 데이터들은 항상 정렬된 상태이며 데이터와 데이터 사이의 범위를 이용해 자식 노드를 가진다.
   • leaf node끼리 linked list로 연결되어 있어 순차적인 범위 탐색에 유리하다.
2. Hash
   • 탐색시간이 O(1)로 제일 빠르다. 충돌 시 최악의 경우에 O(n)이 될 수 있지만 평균적으로 O(1)이다.
   • 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근한다.
   • 값이 정렬되어 저장된 것이 아니므로 특정 기준보다 크거나 작은 값을 찾아야 할 때 매우 비효율 적이다.

 

Scan

1. Table Full Scan
   • 테이블의 전체 블록을 읽어서 사용자가 원하는 데이터를 찾는 방식이다.
2. Index Range Scan
   • 인덱스를 이용하여 필요한 범위의 리프 노드만 탐색하는 방식이다. 

 

Index의 장단점

• 장점: Full scan보다 빠르게 데이터에 접근할 수 있다.
• 단점: insert, update, delete 시 속도가 저하된다. 정렬 상태를 유지해야 하고, 테이블 이외의 인덱스 테이블에도 insert, update를 해줘야 하기 때문에 insert, update가 빈번히 일어나는 테이블에 대해서 성능에 부정적 영향을 줄 수 있다. 

 

reference

github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#index

wangin9.tistory.com/entry/B-tree-B-tree

velog.io/@hygoogi/%EA%B8%B0%EC%88%A0-%EB%A9%B4%EC%A0%91-%EC%A7%88%EB%AC%B8-%EB%AA%A8%EC%9D%8C

wedul.site/403