수직적 탐색 수평적 탐색

데이터베이스 시스템에서 인덱스 탐색은 수직적(Vertical) 탐색과 수평적(Horizontal) 탐색이라는 두 가지 핵심 메커니즘을 기반으로 동작한다. 이 두 방식은 주로 B+tree 구조에서 상호 보완적으로 작용하여 효율적인 데이터 접근을 가능하게 한다.

 

 

수직적 탐색

 

수직적 탐색은 루트 노드에서 시작하여 브랜치 노드를 거쳐 리프 노드까지 하향식으로 진행되며, 각 계층에서의 키 값 비교를 통해 탐색 범위를 점진적으로 축소시킨다. 이때 상위 노드들의 키 값은 순수한 라우팅 용도로만 사용되며, 실제 데이터와의 직접적인 연관성은 없다.

 

수평적 탐색

 

수평적 탐색은 B+tree의 리프 레벨에서 발생하는 선형적 탐색 방식이다. 리프 노드들은 양방향 연결 리스트 형태로 구성되어 있어, 순차적인 데이터 접근이 가능하다. 이러한 구조적 특성은 범위 기반 검색 작업에서 특히 효과적으로 작용한다.

 

 

주요 인덱스 스캔 방식

 

Unique Scan

SELECT * FROM employees 
WHERE emp_id = 1;

 

단일 값을 찾는 순수한 수직적 탐색 방식이다. 루트 노드에서 시작하여 브랜치, 리프 노드까지 한 방향으로 내려가며 정확히 하나의 값을 찾는다. Primary Key나 Unique 인덱스에서 '=' 조건으로 검색할 때 사용된다.

 

 

Range Scan

 

SELECT * FROM employees 
WHERE salary BETWEEN 50000 AND 60000;

 

범위 검색을 위한 복합 탐색 방식이다. 먼저 수직적 탐색으로 범위의 시작점을 찾은 후, 리프 노드 레벨에서 수평적으로 이동하며 조건에 맞는 데이터를 순차적으로 검색한다. BETWEEN, LIKE, 부등호 조건 등에서 사용된다.

 

Index Full Scan

 

-- ORDER BY로 정렬이 필요한 경우
SELECT * FROM employees 
ORDER BY emp_id;

-- 인덱스 컬럼만으로 조회하는 경우
SELECT emp_id, name 
FROM employees;

 

인덱스의 모든 데이터를 순차적으로 읽는 방식이다. 수직적 탐색 없이 리프 노드의 첫 번째 블록부터 마지막 블록까지 수평으로 전체 스캔한다. 주로 정렬된 결과가 필요하거나 인덱스가 테이블의 대부분의 데이터를 포함할 때 사용된다.

 

Index Skip Scan

-- 성별, 나이로 구성된 복합 인덱스 생성
CREATE INDEX idx_emp_gender_age 
ON employees (gender, age);

-- 복합 인덱스를 제대로 활용하는 쿼리
SELECT * FROM employees 
WHERE gender = 'M' AND age = 30;

-- Index Skip Scan이 발생하는 쿼리
SELECT * FROM employees 
WHERE age = 30;

 

복합 인덱스에서 특별한 형태의 탐색 방식이다. 예를 들어 (성별, 나이) 복합 인덱스에서 성별은 건너뛰고 나이로만 검색할 때 사용된다. 첫 번째 컬럼(성별)의 Distinct Value가 적고 두 번째 컬럼(나이)의 선택도가 좋을 때 효과적이다. 옵티마이저는 선행 컬럼의 모든 Distinct Value에 대해 수직적 탐색을 수행하고, 각각에 대해 후행 컬럼 조건에 맞는 데이터를 찾는다.

 

참고

인덱스 탐색 과정, 수직적 및 수평적 탐색 : 네이버 블로그

인덱스 탐색 과정, 수직적 및 수평적 탐색

 

인덱스 수직적 탐색과 수평적 탐색

인덱스 수직적 탐색과 수평적 탐색