Index, 인덱스

 

정의

• 데이터 레코드에 빠르게 접근하기 위해 <column, pointer(위치를 가리킴)> 쌍으로 구성되는 데이터 구조
• Index가 없으면 특정한 값을 찾기 위해 모든 데이터 페이지를 뒤지는 FULL TABLE SCAN이 발생

 

 

원래 DB Table의 Column인 Data를 인덱스 생성함

SMITH는 Location을 통해서 직접 접근 가능

 

 

 

나오게 된 배경

• DB의 양 (row) 가 많아짐에 따라 실행 속도가 차이가 나기 시작함(합 연산)
• JOIN을 할 때마다 실행 속도가 차이 나기 시작함(곱 연산)
• 서브 쿼리를 할 때 마다 실행 속도가 차이 나기 시작함(곱 연산)
• 테이블 자체가 커짐에 따라 테이블에 연산을 적용하는 것이 슬로우 쿼리를 만들게 됨

 

 

목적

• RDBMS의 검색 성능 향상
• SELECT 쿼리의 WHERE 절이나 JOIN 키워드를 사용했을 때 쓰임
• 고유 제약 조건 실현 (중복된 항목이 등록되는 것을 금지하는 고유 인덱스 경우)
• 인덱스 생성 시, 데이터 오름차순 정렬(default)

 

특히 WHERE 절에서 빛을 발하는데

위의 그림과 같이

WHERE NAME = "SMITH" 라는 조건절이 붙는다면

INDEX TABLE SCAN으로 해당 데이터만 검색하므로 빠르게 찾아서 연산할 수 있다.

 

또한 INDEX는 정렬된 형태를 띄고 있기 때문에

ORDER BY 와 같은 부하가 큰 연산을 하지 않아도 된다.

 

정렬되었기에 최솟값과 최댓값이 존재하는 자료형의 경우 쉽게 찾아낼 수 있다. 

 

 

단점

• DB에 추가적인 공간 필요(기존 DB의 10% 정도 더 필요함)
• 인덱스 생성에 시간이 소요됨
• 데이터 변경 작업이 자주 일어날 경우에 인덱스를 계속 정렬해주어야 하기에 성능에 영향을 줄 수 있음
• INDEX가 유용하게 작업되려면 INSERT, UPDATE, DELETE 문이 거의 없는 테이블에서 해야 함
• INDEX 가 유용하게 작용하는 데이터 수는 총 데이터 수의 10%~15% 이하를 처리할 때

 

 

 

장점이 단점보다 많아서 무조건 쓰는 것이 유리하다고 생각할 수 있지만

인덱스가 많은 테이블에 INSERT, DELETE, UPDATE 가 일어난다면 INDEX의 특성인 정렬 때문에

DB의 부하가 높아진다.

 

 

 

인덱스를 잘 사용하는 방법★★★

1. 조건절에 자주 사용하는 column을 파악
2. 최대한 중복되지 않는 값이 좋음(Primary Key, PK)가 가장 좋음 
3. ORDER BY에 자주 사용되는 column
4. JOIN 조건에 자주 사용되는 column

 

 

---

 

대표적인 INDEX 구조

1. B-Tree INDEX
2. B*Tree
3. B+Tree

 

B-Tree(Balanced Tree)

• 인덱스 구성에 많이 사용되는 균형된 m-원 검색 트리
• 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조
• 키 값과 레코드를 가리키는 포인터들이 트리 노드에 오름차순으로 저장됨
• 방대한 양의 자료를 검색하는 경우 효율적

 

 B*Tree

• 구조를 유지하기 위해 추가적인 연산이 필요한 B-Tree의 문제를 보완하기 위해 등장
• Root node를 제외한 모든 node 는 2/3 이상이 채워져야 함
• Node가 가득 차면 분열하지 않고 형제 node에 재배치 , 보조 연산 횟수를 줄임
• B-Tree에 비해 공간 활용도를 높일 수 있다

 

 B+Tree

• B-tree의 순차 접근에 대한 문제 보완
• Leaf node가 linked list 형태로 연결되어 있음
• Non-leaf 노드는 인덱스 역할만 수행함
• 직접 접근에는 index set, 순차 접근에는 sequential set가 사용됨
• 장점 : 순차적인 검색에 효율적임
• 단점 : 어떤 경우에도 leaf노드까지 내려가야 함
• 검색 알고리즘
  

 

 

 

---

 

참고 링크

https://chartworld.tistory.com/18

https://vertabelo.com/blog/database-index-types/