[CS] 인덱스와 해시 테이블

1. 인덱스

1. 인덱스란?

데이터의 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 테이블의 동작속도 즉 조회를 높여주는 자료구조.

• 인덱스를 사용하면 매우 빠른 응답 속도를 얻을 수 있고 쿼리의 부하가 줄어들기 때문에 시스템 전체 성능이 향상되는 효과를 얻음.
• 인덱스 자체 역시 하나의 데이터 덩어리이기 때문에 데이터베이스에 전체 크기의 10%의 추가 공간을 할당해줘야함.
• 변경이 자주 일어나는 경우나 인덱스가 적절하지 않은 경우 성능이 오히려 떨어질 수 있음.

2. 인덱스의 자료구조

1. B-Tree

• 하나의 노드가 여러 개의 자식 노드를 가질 수 있는 균형 트리
• 데이터가 정렬된 상태로 유지
• 탐색, 삽입, 삭제에 일반적으로 O(log N)의 시간 복잡도를 가짐
• 데이터가 리프 노드뿐만 아니라 내부 노드에도 저장될 수 있음

2. B+Tree

• B-Tree를 인덱스에 적합하도록 변형한 자료구조
• 실제 데이터에 대한 정보는 리프 노드에 저장
• 리프 노드끼리 연결되어 있어 순차 탐색과 범위 검색에 유리
• DB 인덱스에서 널리 사용됨

3. Hash 기반 인덱스

• Key에 해시 함수를 적용하여 데이터의 위치를 찾는 방식
• = 와 같은 동등 비교 검색에 유리
• 평균적으로 빠른 검색이 가능
• 데이터가 정렬되어 있지 않기 때문에 범위 검색에는 적합하지 않음

3. 인덱스 타입 종류

	클러스터 인덱스	보조 인덱스
속도	빠르다	느리다
사용 메모리	적다	많다
인덱스	인덱스가 주요 데이터	인덱스가 데이터의 사본
개수	한 테이블에 한 개	한 테이블에 여러 개
리프 노드	리프 노드 자체가 데이터	리프 노드는 데이터가 저장되는 위치
저장값	데이터를 저장한 블록의 포인터	값과 데이터의 위치를 가리키는 포인터
정렬	인덱스 순서와 물리적 순서가 일치	인덱스 순서와 물리적 순서가 불일치

2. 해시 테이블

1. 해시 테이블이란?

해시 함수를 통해 산출된 해시 값을 인덱스로 사용하여 데이터를 저장하는 곳.

서로 다른 키가 해시 함수를 통과하면서 같은 해시 값을 가지게 된다면?

해시 충돌
해시 테이블의 같은 위치에 두 개 이상의 데이터가 저장되려는 현상

해결 방법

1. Chaining 기법
   해시 테이블 저장공간 이외의 공간을 활용하는 기법.
   충돌이 일어나면 해당 인덱스가 가리키는 해시 테이블 공간 뒤로 연결 리스트를 사용하여 추가적으로 연결 시킨 후 저장.
2. Linear Probing 기법
   해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법.
   충돌이 일어나면 해당 해시 값의 다음부터 순회를 하며 처음으로 나오는 빈 공간에 저장하는 방법.