인덱스는 책의 색인과 같은 역할을 하는 데이터베이스 객체로써, 데이터 베이스 테이블의 검색 속도를 향상시켜줄 수 있는 자료구조이며,
칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만든다.
또한, 테이블과는 독립적으로 존재하지만, 테이블에 의존적이기 때문에 해당 테이블이 삭제될 경우 같이 제거된다.
DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 데는 빠르지만 새로운 값을 추가,삭제,수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높인다.
FTS(Full Table Scan) : 테이블을 처음부터 끝까지 검색하는 방법
Index Scan : 인덱스를 검색하여 해당 자료의 테이블을 액세스하는 방법
만약 Index를 적용하지 않은 컬럼을 조회한다면, 전체를 탐색하는 Full Table Scan이 수행된다. 이는 전체를 탐색하기 때문에 처리 속도가 떨어진다.
B+Tree는 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조.
B- Tree가 모든 노드에 데이터를 저장했다면 B+ Tree는 리프노드만이 인덱스와 함께 데이터를 가지고 있고 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(Key)만을 가진다는 차이가 있다. 또한, 리프노드들이 LinkedList로 연결되어 있어서 부등호 연산을 이용한 순차 검색에 용이하다.
B+Tree의 시간 복잡도 O(logN)
일반적으로 사용되는 인덱스 알고리즘으로 balanced tree를 사용. (편향된 트리가 아니도록 밸런스 유지)
칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘.
칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원.
해시 테이블 단점
해시테이블은 데이터 탐색 시 시간복잡도가 O(1)로 매우 빠르다. 하지만, 해시 테이블은 부등호(<, >)를 이용한 연속적인 데이터의 순차 검색이 불가능하다.
DBMS는 인덱스를 항상 최신의 정렬된 상태로 유지시킨다.데이터의 수정, 삽입,삭제 시 다음과 같은 연산을 추가적으로 해주며 그에 따른 오버헤드가 발생한다.
장점
단점
참고자료
https://mangkyu.tistory.com/96
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#index