Selection
Selection 알고리즘은 데이터베이스 쿼리에서 조건에 맞는 레코드를 찾는 데 사용되는 연산입니다.
Selection 연산에는 큰 범위로 두 가지 방법이 있습니다.
Table Scan
전체를 탐색
모든 블럭을 스캔 → 조건에 맞는 레코드 검색
| 설명 | |
|---|---|
| 장점 | 검색 조건, 레코드 저장 순서, 혹은 인덱스의 유무에 관계없이 사용 가능 |
| 단점 | 전체를 순회하여 찾기 때문에 느리고 Read 연산이 많음 |
이진 검색은?
→ 레코드가 순차적으로 저장되지 않으므로(연결 리스트 방식) 일반적으로 적용 불가
Index Scan
인덱스를 사용하여 탐색
-
인덱스는 특정 열(칼럼)을 기반으로 정렬된 데이터 구조로, 검색 속도를 향상시키기 위해 사용
-
만약 WHERE 절에 사용된 조건이 인덱싱되어 있다면, 인덱스를 활용하여 필요한 레코드를 빠르게 찾을 수 있음
-
일반적으로 파일을 전체로 읽는 것보다 효율적입니다.
| 키 특성 | 탐색 비용 |
|---|---|
| primary index | HTi+1 |
| 보조 index (clustered) | HTi + 「SC(A,r) / fr |
| 보조 index (non-clustered) | HTi + SC(A,r) |