Index?

• 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조
• 데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회가 가능
• SELECT, UPDATE, DELETE의 성능이 함께 향상됨 (위 연산들을 수행하려면 해당 대상을 조회해야만 작업이 가능하기 때문에)
• e.g. 책의 색인

Index 관리

• Index는 항상 최신의 정렬된 상태를 유지해야 원하는 값을 빠르게 탐색 가능
• Index가 적용된 컬럼에 INSERT, DELETE, UPDATE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 함(오버헤드 발생)
• INSERT : 새로운 데이터에 대한 인덱스 추가
• DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 진행
• UPDATE : 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가

INDEX 장점

• 테이블을 조회하는 속도와 그에 따른 성능향상
• 전반적인 시스템 부하 감소
• e.g. 규모가 작지 않은 테이블, INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼, JOIN이나 WHERE또는 ORDER BYE에 자주 사용되는 컬럼, 데이터의 중복도가 낮은 컬럼에서 사용되면 좋음

INDEX 단점

• INDEX를 관리하기 위해서 DB에 별도로 약 10%에 해당하는 저장공간이 필요
• 인덱스를 관리하기 위해 추가 작업이 필요
• 인덱스를 잘못 사용할 경우 오히려 성능 저하되는 역효과 발생
• e.g. CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과 발생(DELETE와 UPDATE 연산시 인덱스를 삭제하는게 아니라 사용하지 않음 처리를 해주기 때문)

INDEX의 자료구조

Hash Table

• 데이터, 데이터의 위치를 Key, Value로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스 구현
• 시간복잡도 O(1)
• 해시는 등호(=)연산에만 특화되었기 때문에 값이 1이라도 달라지만 완전히 다른 해시값을 생성하는데, 이러한 특성에 의해 부등호 연산(>,<)이 자주 사용되는 데이터 베이스 검색을 위해서는 적합하지 않음
• 이러한 이유로 데이터베이스의 인덱스에서는 B+ Tree가 일반적으로 사용됨
• e.g. "오늘"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못함

B+ Tree

• 리프노드만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드들은 데이터를 위한 인덱스 만을 갖는 구조
• 리프 노드들은 LinkedList로 연결되어있음
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다
• 시간복잡도 O(log2N)