[DB] 인덱스(Index)

인덱스(Index)

출처

인덱스란 데이터베이스 테이블 내의 특정 열에 대한 검색 및 정렬 성능을 향상시키기 위해 사용되는 자료 구조를 뜻합니다.
인덱스 구조의 유일한 목적은 데이터를 검색하는 동안 디스크의 I/O를 최소화하도록 제한하는 것에 있습니다. 즉 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 및 정렬 성능을 향상시키는 자료 구조로 인덱스가 생성되면 인덱스된 열과 연결된 테이블의 값 위치가 기록됩니다.
인덱스는 특정 열에 대한 정렬된 키와 해당 키가 위치한 데이터 블록에 대한 포인터로 구성되어 있습니다.
테이블의 다른 세부 항목들은 갖고 있지 않기 때문에 보통 테이블을 저장하는데 필요한 디스크 공간보다 작으며 관계형 데이터베이스에서의 인덱스는 테이블 부분에 대한 하나의 사본을 의미합니다.

인덱스는 테이블의 열과 해당 열의 값이 저장된 위치를 포함하는 색인으로 구성되는데 이러한 색인을 통해 데이터베이스 엔진은 원하는 데이터를 빠르게 찾을 수 있습니다.
인덱스는 일종의 도서 색인과 비슷한 역할을 합니다.
특정 단어를 찾기 위해 책의 색인을 확인하면 해당 단어가 어느 페이지에 있는지 빠르게 찾을 수 있는 경우 동일합니다.

페이지(Page)

페이지란 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 데이터의 물리적인 저장 단위이며 디스크 블록(Disk Block)이라고도 불립니다.
일반적으로 4KB, 8KB 등의 고정된 크기로 나눠지며 페이지의 크기는 I/O 연산 성능, 메모리 사용 효율성, 캐시 효과 등을 고려하여 결정됩니다.

또한 하나의 페이지는 여러 개의 블록으로 나눠질 수 있으며 블록(Block)은 데이터베이스에서 물리적인 I/O 연산의 최소 단위이며 페이지는 논리적인 데이터의 최소 단위입니다.

페이지 구성요소

1. 헤더(Header): 페이지의 메타데이터를 저장하는 곳으로 페이지 번호, 레코드 수, 다음 페이지의 주소 등이 포함됩니다.
2. 레코드(Record): 실제 데이터가 저장되는 부분으로 테이블의 행에 해당하는 데이터를 포함합니다.
3. 공간 예약 영역(Free Space): 새로운 데이터 삽입이나 기존 데이터의 수정으로 인해 발생하는 여유 공간입니다.
4. 테일(Tail): 페이지의 끝 부분을 가리키는 포인터로 다음 페이지에 대한 정보가 저장됩니다.

장점

• 검색 속도 향상: 테이블의 레코드는 내부적으로 일정한 순서 없이 저장되게 되는데 특정 조건에 맞는 데이터를 조회하기 위해서는 레코드를 풀 테이블 스캔(Full Table Scan)을 하게 됩니다. 하지만 WHERE 절에 포함된 조건에 해당하는 인덱스를 사용하면 데이터베이스는 해당 조건을 만족하는 행만을 실제 테이블에서 찾는 대신 인덱스를 통해 빠르게 결과를 가져올 수 있습니다.
• 정렬 속도 향상: 데이터베이스에서 정렬은 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생됩니다. 부하가 많이 걸리는 작업을 전반적인 자원의 소모 없이 ORDER BY 절에 사용된 열에 인덱스가 있다면 데이터베이스는 해당 인덱스를 활용하여 빠르게 정렬된 결과를 반환할 수 있습니다.
• 옵티마이저 힌트 활용: 옵티마이저는 가장 효율적인 방법으로 SQL을 수행할 최적의 처리 경로를 생성해주는 DBMS의 핵심 엔진으로 인덱스를 사용하면 옵티마이저가 효과적인 실행 계획을 수립할 수 있는 추가적인 정보를 제공합니다.
• 중복 행 제거 및 유일성 보장: 유니크 인덱스를 사용하면 해당 열에 중복된 값을 방지하고 검색 및 정렬 시에 유일한 값을 보장할 수 있습니다.
• 클러스터 인덱스를 이용한 성능 개선: 클러스터 인덱스는 테이블의 데이터 순서를 변경하여 인덱스를 통한 검색 속도를 향상시킵니다. 특히 BETWEEN, >, < 와 같은 범위 검색이나 정렬된 결과를 필요로 하는 경우에 유용합니다.

단점

• 저장 공간 소모: 인덱스는 추가적인 저장 공간을 필요로 합니다. 인덱스는 주로 데이터베이스의 약 10%에 해당하는 저장공간이 필요하며 테이블에 인덱스를 많이 추가하면 데이터베이스 크기가 커질 수 있습니다. 특히 대량의 데이터가 있는 경우 인덱스의 크기가 상당히 커질 수 있습니다.
• 유지 비용: 데이터의 추가, 수정, 삭제와 같은 쓰기 작업을 통해 통해 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬해야 하므로 성능에 영향을 미칠 수 있습니다. 인덱스 갱신 작업이 추가되기 때문에 쓰기 작업이 느려질 수 있습니다.
• Lock: 인덱스 업데이트 작업은 트랜잭션 동안 락(lock)이 걸리게 되기 때문에 다른 트랜잭션의 쓰기 작업이 블록될 수 있습니다. 동시성 문제로 성능 감소로 이어질 수 있습니다.

자료구조

해시 인덱스(Hash Index)

출처

해시 인덱스는 해시 함수를 사용하여 데이터를 해시 버킷에 저장하여 키를 해시 함수를 통해 해시 값으로 변환하고 이 값을 인덱스로 사용합니다.
해시 함수의 결과 값을 저장하므로 키 컬럼의 데이터 사이즈에 상관 없이 낮은 용량의 해시 값으로 저장되기 때문에 실제 해시 인덱스에 저장되는 값의 용량은 상당히 줄어듭니다.
또한 트리 형태의 구조가 아니므로 검색하고자 하는 값을 해시 함수를 통해 키값이 포함된 버켓을 조회해 실제 레코드가 저장된 위치를 빠르게 알 수 있습니다.
즉 해시 인덱스의 큰 장점은 실제 키값과는 관계없이 인덱스 크기가 작고 검색이 빠르다는 것입니다.

하지만 데이터베이스 인덱스에서 해시 인덱스는 동등 비교 검색에는 최적화 되어 있지만 범위를 검색, 정렬된 결과를 가져오는 목적으로는 사용할 수 없다는 제한 사항이 있습니다.
해시 인덱스는 빠른 검색을 제공하지만 키값 자체가 변환되어 저장되기 때문에 범위를 검색하거나 원본 값 기준으로 정렬할 수 없습니다.
또한 다중 컬럼으로 생성된 해시 인덱스에서도 모든 컬럼이 동등 조건으로 비교되는 경우에만 인덱스를 사용할 수 있다는 주의 점이 있습니다.

B-Tree

출처

B-Tree는 자식 2개만을 갖는 이진 트리(Binary Tree)를 확장하여 N개의 자식을 가질 수 있도록 개선한 구조입니다.
항상 균형을 맞추고 있다는 의미에서 균형 트리(Balanced Tree)라고 불립니다.

출처

B-Tree의 경우 모든 노드에서 인덱스(Key)와 테이블 행을 참조하는 데이터(Value)를 가지고 있습니다.
키는 인덱스 구조 내부에서 테이블 행을 찾는데 사용되고 데이터는 인덱스 외부에서 테이블 행을 찾는데 사용됩니다.

B-Tree에서 특정 데이터에 액세스하기 위해 루트에서 시작하여 리프 노드까지 탐색되며 도중에 키를 비교하여 경로를 선택합니다.
일치하는 모든 레코드를 찾을 때까지 탐색을 계속하며 모든 레코드를 찾았다면 디스크에서 실제로 데이터를 가져오게 됩니다.
트리 순회는 트리 깊이에 따라 쿼리 성능에 큰 영향을 미칠 수 있습니다.

디스크 검색은 선형 작업이지만 기본적으로 B-Tree 인덱스의 경우 트리 순회하기 때문에 범위 검색과 정렬된 순서로 데이터에 접근하는데 선형 작업보다 더 좋은 성능을 발휘합니다.

B+Tree

출처

B+Tree는 B-Tree를 확장하여 특히 범위 쿼리와 정렬된 데이터에 뛰어난 성능을 제공하는 인덱스 구조입니다.
B+Tree는 모든 노드에 인덱스 값을 저장했던 B-Tree와 다르게 다음과 같은 다른 특성을 가지고 있습니다.

1. B+Tree의 리프 노드는 모두 연결된 리스트(LinkedList)로 연결되어 있습니다.
2. B+Tree의 리프노드만 인덱스(Key)와 함께 데이터(Value)를 가지고 있고 나머지 노드들은 데이터를 위한 인덱스만을 갖습니다.

출처

위와 같은 B+Tree만의 특성으로 인해 데이터를 찾기 위해 리프노드까지 탐색하는 경우 모든 리프 노드가 LinkedList로 연결되어 있기 FULL SCAN 시 리프 노드들만 순차 탐색하면 되기 때문에 범위 탐색에 유리합니다.

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.