99클럽 코테 스터디 5일차 TIL DB Hash Indexes

• DB
  • Index
    • Index 작동 원리
    • Index 종류
      • B-Tree 인덱스
      • Hash Indexes
      • Bitmap Index
      • GIST(Generalized Search Tree)
      • R-Tree
      • Full Text Index
      • Spatial Index
      • Trie(Prefix Tree) Index
      • Covering Index
  • 영속성
  • 트랜잭션
  • ORM
  • ACID
  • N+1 문제
  • DB 정규화
  • Data Replication
  • sharding 전략
  • CAP 이론

---

Hash Index

• 데이터의 위치를 Hashing 을 통해 Index 를 저장하는 방식
  • hasing?
    • 특정한 hash function을 정의하여 이를 통해 key 값을 일정한 범위의 수로 변환하는 작업
• 등가 검색(equal searches) 에 매우 효과적

작동 원리

1. key 값의 해시화
   • 데이터를 인덱스에 추가할 때, 키 값에 해시 함수를 적용해 고유한 해시 코드를 생성함. ➡️ 데이터가 저장될 위치를 결정함.
2. HashTable
   • 해시 인덱스는 보통 해시 테이블을 사용하여 구현됨. 해시 테이블은 배열과 유사한 구조로, 각 셀은 특정 해시값에 해당하는 데이터의 위치 정보를 가지로 있음.
3. 충돌 처리
   • 서로 다른 key 값이 동일한 해시 값을 가질 때 충돌(collision) 이 발생함. 이를 처리하기 위해 일반적으로 체이닝(chaining) 이라는 방법을 사용함. ➡️ 같은 해시값을 가진 요소들을 연결 리스트로 연결하는 것을 의미

장점

1. 빠른 검색 속도
   해시 인덱스는 key 값으로 직접 데이터 위치를 찾기 떄문에 검색 속도가 매우 빠름. 이론적으로는 상수 시간 복잡도인 O(1) 을 가짐.
2. 간단한 구조
   해시 테이블 구조는 상대적으로 구현이 간단하며, 데이터 접근도 직관적임.

단점

1. 범위 검색 비효율적임
   • 해시 인덱스는 범위검색(특정 범위의 값 찾기)에 적합하지 않음. 해시 함수의 특성상 연속적인 값을 연속적인 위치에 저장하않기 때문
2. 메모리 사용량
   충돌이 많이 발생하는 경우, 많은 양의 메모리를 사용할 수 있으며, 체이닝으로 인해 오버헤드가 발생할 수 있음.

어디다 적용?

주로 등가 조건 검색이 많은 시나리오에서 유용함. 특히 메모리 내 데이터베이스나 캐싱 시스템에서 선호됨. 값의 정확한 일치를 찾는 작업에서 해시 인덱스의 성능이 크게 돋보일 수 있음.