반응형
1. 인덱스의 정의
- 인덱스(Index)는 테이블의 특정 컬럼(column)에 대해 검색 속도를 높이기 위해 추가로 만든 자료 구조
- 책의 목차처럼, 원하는 데이터가 테이블 전체를 뒤지지 않고도 바로 위치를 찾을 수 있게 해주는 구조
2. 인덱스의 종류
1) B-Tree 인덱스 (가장 흔함)
- 균형 이진 트리(B+Tree) 구조 사용
- 장점:
- 특정 값 검색: O(log n)
- 범위 검색: 효율적 (e.g., WHERE age BETWEEN 20 AND 30)
- 사용 예시: PRIMARY KEY, UNIQUE 인덱스
2) Hash 인덱스
- 해시 테이블 기반
- 장점:
- 정확한 값 검색: O(1) 평균
- 단점:
- 범위 검색에는 부적합
- 사용 예시: MySQL MEMORY 엔진
3) 기타
- Full-text 인덱스: 문자열 검색 최적화
- Spatial 인덱스: 지리정보 데이터 최적화
- Composite(복합) 인덱스: 여러 컬럼 조합 검색에 사용
B-Tree 와 Hash Index 시간 복잡도 비교
| 연산 종류 | B-Tree (또는 B+Tree) | Hash | 설명 |
| 정확한 값 검색 (Equality lookup) | O(log N) | O(1) 평균O(N) 최악 | Hash는 정확 검색에 특화된 순간이동 느낌. B-Tree는 계층을 타고 내려가는 구조. |
| 범위 검색 (Range query) | O(log N + K) | 불가능 | Hash는 키→버킷 맵핑이라 순서를 모름. B-Tree는 정렬된 상태라 범위 탐색 가능. |
| 정렬된 순회 (Ordered scan) | O(N) | 불가능 | Hash는 정렬 상태를 유지하지 않음. |
| 삽입 (Insert) | O(log N) | O(1) 평균O(N) 재해시 발생 시 | Hash는 공간 부족 시 전체 테이블 재정비가 필요해 최악이 무겁다. |
| 삭제 (Delete) | O(log N) | O(1) 평균 | Hash는 버킷만 정리하면 OK. |
| 메모리 사용량 | 중간 | 큼 | Hash는 충돌 방지를 위해 여분 메모리를 더 들고 다닌다. |
반응형
'DataBase > MySQL' 카테고리의 다른 글
| [MySQL] 행, 열 변환 작업 (0) | 2021.08.04 |
|---|---|
| [MySQL] AUTO_INCREMENT 초기화 (0) | 2021.02.01 |
| [MySQL] WITH 재귀(RECURSIVE) 쿼리 계층구조 (0) | 2020.07.20 |
| [MySQL] CASE 문 (0) | 2020.07.20 |
| [MySQL] DATE_FORMAT 날짜데이터 형식 변환 (0) | 2020.07.20 |









