[DB] Index Structures (인덱스 구조)

서론 : 

DBMS에 따라 처리단위가 다르다 (ex. Oracle - Block단위 , MySQL - Page 단위)

page가 클수록 효율적인 것은 아님, 적절한 Size가 제일 좋음

 

정의 : 

Index는 목차이며, data를 찾을때 처음부터 끝까지 확인하는 것을 방지해 준다.

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색속도를 향상시킬 수 있다.

장단점 : 

장점

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

단점

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

 

자료구조 종류

 

1. 해시 테이블(Hash Table)

(Key, Value)로 데이터를 저장하는 자료구조, 빠른 데이터 검색이 필요할때 유용하다.

Key값을 이용해 고유한 index를 생성하고 그것을 활용한다.

시간 복잡도는 O(1)

 

2. B+ Tree

 자식 노드가 2개 이상인 B Tree를 업그레이드 시킨 자료구조이다.

 

• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
• 리프노드들은 LinkedList로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

 

O(logn)의 시간복잡도를 가지지만 해시테이블보다 인덱싱에 더욱 적합하다.

 

 

---

참고 : 

https://jeong-pro.tistory.com/114

https://mangkyu.tistory.com/96

https://chartworld.tistory.com/18

https://jungwoong.tistory.com/34