[데이터베이스] DB에서 인덱스는 왜 필요할까?

인덱스란?

데이터베이스에서 인덱스(Index) 는 책의 목차처럼, 원하는 데이터를 더 빠르게 조회 하기 위한 자료 구조이다. 테이블에 있는 데이터를 모두 훑어보는 Full Table Scan을 줄이고, 필요한 데이터의 위치를 빠르게 찾도록 도와준다.

👉 결국 “빠른 검색” 이 인덱스의 목적!

인덱스가 없다면 어떤 문제가 생길까?

예를 들어, 5천만 명의 사용자 중에서 이름이 “철수”인 사람을 찾는다고 해보자. 인덱스가 없다면, DB는 모든 행을 일일이 비교하며 탐색해야 하므로 O(n) 의 시간이 걸릴 것이다.

하지만 인덱스를 사용하면 훨씬 적은 비교로도 원하는 데이터를 찾을 수 있기 때문에 시간을 단축시킬 수 있다.

인덱스 구현 방식 중 하나 - 해시 기반 인덱스

✨ 해시 테이블 기반 인덱스

해시 테이블은 키-값 쌍을 매핑하는 자료 구조이다. 주어진 키에 대해 해시 함수를 적용하여 배열의 오프셋(offset) 을 계산하고, 그 위치에 값을 저장하거나 조회한다.

• 평균 시간 복잡도: O(1)
• 최악 시간 복잡도: O(n) (해시 충돌이 심한 경우)

DB에서는 “상수 시간”도 중요하다. 왜냐하면 실제 환경에서는 상수의 크기(캐시 미스, 디스크 접근 등)가 성능에 큰 영향을 주기 때문이다.

Static Hashing: 정적 해싱

정적 해싱에서는 고정된 크기의 해시 테이블 을 사용한다. 이 크기는 생성 시점에 결정되며, 이후에 변경되지 않는다.

Approach #1: Linear Probe Hashing

• 하나의 거대한 배열을 사용한다.
• 해시 충돌(Collision)이 발생하면 다음 빈 공간을 선형적으로 탐색 하여 저장한다.
• 조회, 삭제 시에도 같은 방식으로 탐색한다.

⚠️ 클러스터링(Clustering)이 발생하여 성능 저하가 일어날 수 있다.

클러스터링(Clustering)은 해시 충돌이 반복되면서 연속된 슬롯에 데이터가 몰리는 현상을 말한다. 예를 들어, 어떤 키가 5번에 할당되었지만 이미 5번을 다른 키가 사용 중이라 6, 7, 8번 등 다음 슬롯을 계속 확인하면서 데이터를 저장하는 상황이 있을 수 있다. 이렇게 되면 빈 공간이 중간에 끼어 있어도 앞에서부터 많은 탐색을 요구하게 되어 조회, 삽입 속도가 느려지는 문제가 생긴다.

이게 왜 문제냐면, 선형 탐사 방식은 충돌이 발생할수록 탐색 범위가 점점 길어지기 때문이다. 빈 공간이 존재하더라도 앞쪽에 클러스터가 생기면 접근 시간이 길어진다.

결국 평균적으로 검색, 삽입, 삭제 성능이 저하될 수 있다.

Approach #2: Robin Hood Hashing

• Linear Probe Hashing의 개선 버전으로, 삽입 시 충돌이 발생했을 때 기존 키와의 이탈 거리 를 비교하여 더 멀리 떨어진 키( “가난한” 키)가 가까운 키( “부자” 키)로부터 자리를 빼앗는 방식이다.
• 각 키는 자신의 최적 위치로부터 몇 칸 떨어져 있는지를 추적, 저장한다.
• 즉 더 많은 충돌을 겪은 키가 충돌을 덜 겪은 키보다 우선권을 가지며, 이로써 전체적으로 더 공평한 분포를 만든다.

Approach #3: Cuckoo Hashing

• 두 개 이상의 해시 테이블과 서로 다른 해시 함수 를 사용하는 충돌 해결 기법이다.
• 이름은 뻐꾸기(Cuckoo)가 다른 새의 둥지에 있는 알을 밀어내고 자신의 알을 낳는 습성에서 유래되었는데, 이처럼 삽입 시 충돌이 발생하면 기존 원소를 쫓아내고 삽입하려던 원소를 삽입한다. 이때 밀려난 원소는 다른 해시 함수로 계산된 위치에 삽입한다.
• 이러한 특징으로 인해 조회와 삭제는 항상 O(1)이지만, 쫓아내고 쫓아내는 과정이 반복되면(루프) 재해시(rehash)가 필요할 수 있다.

Observation: 정적 해싱의 한계

정적 해싱(Static Hashing)은 해시 테이블 크기를 사전에 고정 해야 한다. 즉, 테이블이 감당할 수 있는 최대 키 개수나 부하율(load factor)을 미리 예측해야 하며 데이터의 크기가 일정하다는 전제를 필요로 한다.

하지만 현실 세계의 데이터는 대개 증가하거나 감소 한다. 이 경우 다음과 같은 문제가 발생한다.

데이터가 많아질 경우

• 충돌이 급격히 늘어나고, 충돌 처리가 느려진다.
• 일정 수준을 초과하면 전체 해시 테이블을 새 크기로 재구성해야 한다.
• 이때 기존 데이터 전부를 새 테이블에 재삽입하는 데 O(n) 이상의 비용이 발생한다.

데이터가 줄어들 경우

• 테이블에서 낭비되는 공간을 계속 유지 하게 된다.
• 메모리 비효율성과 캐시 활용 저하로 이어진다.

따라서 키 개수가 고정되거나, 매우 적게 변동되는 환경에서 쓰면 좋고, 특히 임베디드 시스템 같은 곳에서 쓰면 좋다.

이러한 한계를 해결하기 위한 것이 바로 동적 해싱(Dynamic Hashing) 이다.

Dynamic Hashing: 동적 해싱

동적 해싱은 필요에 따라 테이블의 크기를 조절 할 수 있는 기법이다. 테이블을 처음부터 크게 만들 필요가 없고, 데이터가 많아질수록 자동으로 크기가 커진다. 즉, 데이터의 삽입과 삭제에 따라 테이블 구조를 유연하게 확장하거나 축소할 수 있다.

대표적인 방식:

• Chained Hashing
• Extendible Hashing
• Linear Hashing

🔸 Chained Hashing

• 각 슬롯마다 연결 리스트(bucket list) 를 둔다.
• 같은 해시 값을 가지는 키가 들어오면 해당 슬롯의 리스트에 추가한다.
• 충돌이 발생해도, 리스트만 늘어나므로 구조를 변경하지 않아도 된다.

단점: 연결 리스트가 길어질 경우, 조회 성능 저하 발생

🔸 Extendible Hashing

• 기본은 Chained Hashing이지만, 버킷이 너무 커지면 분할(split) 한다.
• 여러 슬롯이 같은 버킷 체인 을 가리킬 수 있다.
• 이때 특정 버킷만 분할하여 데이터 이동을 최소화 한다.
• 해시 키에서 사용하는 비트 수 를 늘려 테이블을 확장한다.

작동 방식 상세 설명

Extendible Hashing은 해시 충돌이 발생할 때 전체 테이블을 재구성하지 않고, 충돌이 발생한 특정 버킷만 선택적으로 분할 함으로써 효율적으로 확장한다.

• 해시 키의 일부 비트만 사용하여 테이블 내 위치를 결정하고, 필요할 때마다 사용하는 비트 수(global depth)를 증가 시켜 디렉토리를 확장한다.
• 하나의 버킷을 여러 디렉토리 엔트리가 공유 할 수 있기 때문에 테이블 공간을 더 유연하게 사용할 수 있다.
• 각 버킷은 자신만의 local depth(현재 몇 비트까지 사용하는지) 정보를 갖고 있으며, 해당 비트까지 충돌이 나면 그때만 분할이 발생한다.

global depth: 디렉토리에서 사용하는 해시 키의 비트 수

local depth: 특정 버킷에서 구분 가능한 비트 수

🔸 Linear Hashing

• 해시 테이블이 포인터(split pointer) 를 유지한다.
• 어떤 버킷에서든 오버플로우가 발생하면, 현재 포인터 위치의 버킷을 분할한다.
• 포인터가 마지막 슬롯까지 도달하면, 다시 처음으로 돌아가서 해시 함수를 한 단계 확장한다.

즉, 해시 테이블의 버킷을 점진적으로 분할하면서 오버플로우와 공간 낭비 문제를 완화하는 동적 해싱 기법이다. 공간 활용률이나 오버플로우 평균 길이에 따라 분할 시점을 결정할 수 있어 유연하지만, 해시 함수와 포인터 로직 관리가 복잡하다..

마무리

정리 항목	Static Hashing	Dynamic Hashing
크기 조절	불가능	가능
초기 설계 유연성	낮음	높음
삽입 성능	빠름 (충돌 시 성능 저하)	안정적 (구조 변화로 대처)
대표 기법	Linear Probe, Robin Hood, Cuckoo	Chained, Extendible, Linear

해시 테이블은 DB 내부에서 빠른 조회가 필요한 캐시 구조 등에 적합하지만, 테이블 인덱스 용도로는 일반적으로 B+Tree 가 선호된다. 왜일까? 정렬과 범위 검색 때문

다음 포스팅 예고

B+Tree

→ aka “The Greatest Data Structure of All Time”