인덱싱과 해싱(and Vector DB에의 적용)

벡터 DB를 공부하다가 DB에서 사용하는 기술인 인덱싱과 해싱에 대해 궁금해져서 정리해보았다.

 

보통 인덱싱과 해싱을 같이 사용하는 경우가 많아서 내 머릿속에서 이 개념이 혼재되어 있었다. 

두개의 개념과 차이점, 그리고 어떻게 함께 쓰이는지, 정리해 보겠음!

 

인덱싱이란?

데이터를 빠르게 찾기 위해서 데이터의 위치 정보를 저장하는 일

 

how?

검색을 빠르게 하기 위한 데이터 구조를 만든다.

트리, 그래프, 리스트 등으로 데이터의 위치 정보를 저장한다. 

 

trade off는?

인덱싱의 장점은 검색 속도를 높이는 것이다. 저장된 데이터의 위치 정보를 바탕으로 빠르게 데이터를 찾을 수 있다. 

데이터의 위치 정보를 저장하는 데에 추가적인 메모리를 사용한다. 인덱싱을 사용하지 않는 경우에는 추가적인 메모리 사용하지 않지만 전체 데이터를 탐색해야하므로 시간복잡도 up!

---

 

"해싱한다"란?

임의의 데이터를 해시 함수에 넣어 그 결과로 고정된 크기의 고유 해시값을 생성한다.

 

해싱의 특징은?

 

• 고정된 크기의 출력 → 입력 데이터의 크기가 달라도, 해시값은 고정된 크기로 생성됨.
• 유일성 → 서로 다른 입력 데이터는 서로 다른 해시값을 가지도록 설계됨.
• 일방향성 → 해시값으로부터 원본 데이터를 역으로 계산할 수 없음.

 

해싱의 사용

• 고정된 크기의 출력 : 해시값을 고정된 크기로 유지해야만, 해시 테이블 같은 자료구조에서 일관되게 사용
• 유일성: 중복 데이터 방지, 무결성 검증 등에 사용
• 일방향성: 보안, 암호화 등에 사용

해시함수는 왜 이런 특성을 가지고 있는가?

 

 

해시 함수는 특정 개인의 발명이 아니라, 컴퓨터 과학과 암호학의 발전 속에서 여러 연구자와 기관들의 기여로 발전된 기술이다. 초기에는 데이터 검색 최적화를 위한 목적으로 개발되었지만, 이후 데이터 무결성 보장, 암호화, 블록체인 등 다양한 분야에서 필수 기술로 자리 잡았다. 현재까지도 NIST, NSA, MIT, Google과 같은 기관과 학자들이 해시 함수의 보안성과 효율성을 발전시키고 있다.

1. 수학적 복잡성

해시 함수는 수학적으로 복잡하고 무작위성(Randomness)을 고려하여 설계된다. 이를 통해 충돌을 최소화하고, 입력값의 패턴이 해시값에 드러나지 않도록 한다.

2. 모듈로 연산 (Modulo Arithmetic)

해시 함수는 종종 모듈로 연산을 통해 해시값을 생성하여, 값이 일정 범위 내에 존재하도록 한다.

3. 비선형성 (Non-linearity)

해시 함수는 입력값과 출력값의 관계가 선형이 아닌 비선형적으로 설계된다. 이를 통해 작은 입력 변화에도 해시값이 급격히 변화하도록 한다. 이러한 특성은 Avalanche Effect라고도 불린다.

4. 분포 균일성 (Uniform Distribution)

해시 함수는 입력값이 고르게 해시값으로 분포되도록 설계된다. 이는 해시 테이블에서 데이터가 특정 위치에 몰리지 않도록 하여, 검색 속도를 일정하게 유지할 수 있도록 한다.

 

 

VectorDB에서의 인덱싱과 해싱 기술 -> 검색 최적화를 위한 기술

VectorDB에서는 **인덱싱(Indexes)**과 해싱(Hashing) 기술을 통해 유사도 기반 검색의 속도와 정확성을 향상시켰다. 이 두 가지 기술은 대규모 데이터셋에서도 효율적인 검색을 가능하게 하는 핵심 기술로 사용된다.

1. 인덱싱 기술

• HNSW (Hierarchical Navigable Small World): 그래프 기반 인덱싱 방식으로, 벡터 간의 유사성을 빠르게 탐색할 수 있도록 지원한다. 계층적 구조로 인해 검색 속도가 빠르고 정확성이 높은 것이 특징이다.
• IVF (Inverted File Index): 벡터 데이터를 클러스터로 나누고, 각 클러스터에 인덱스를 부여하여 검색 속도를 향상시킨다. 검색 시 해당 클러스터만 탐색하므로 효율적이다.
• Flat Index: 모든 벡터를 단순히 저장하는 방식으로, 검색 정확도는 높지만 속도는 느릴 수 있다. 작은 데이터셋에 적합하다.

2. 해싱 기술

• LSH (Locality-Sensitive Hashing): 유사한 벡터가 동일한 해시값을 가지도록 설계된 해싱 방법이다. 이를 통해 유사한 벡터들을 빠르게 필터링하고, 검색 범위를 좁힐 수 있다.
• Hash Table: 해시값을 기반으로 벡터를 분류하고 저장하여, 해시값이 일치하는 후보 벡터만 우선적으로 검색하도록 구성된다.

3. 인덱싱과 해싱 기술의 역할과 검증

• 인덱싱 기술은 데이터의 구조를 최적화하여 대규모 데이터셋에서도 빠르게 유사 벡터를 검색할 수 있도록 한다. 특히 HNSW와 IVF는 검색 속도와 정확성을 모두 향상시키는 데 기여한다.
• 해싱 기술은 유사한 데이터가 동일한 해시값으로 매핑되도록 하여, 검색 범위를 효과적으로 제한하고, 검색 속도를 비약적으로 향상시킨다.
• 이러한 두 기술은 VectorDB에서 유사도 기반 검색을 빠르고 정확하게 처리하는 데 핵심적인 역할을 한다고 볼 수 있다. 특히 대규모 데이터 환경에서는 이 두 기술이 결합되어야만 검색 성능을 최적화할 수 있다.

따라서 인덱싱과 해싱 기술은 VectorDB에서 핵심적인 검색 최적화 기술로 작용하며, 두 기술 모두 빠르고 정확한 유사도 기반 검색을 구현하는 데 필수적이다.