99클럽 코테 스터디 11일차 TIL DB Trie(Prefix Tree) Index

• 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 이론

---

란?

• 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 데이터 구조
• 문자열 집합에서 공통 접두사를 공유하는 문자열을 효율적으로 관리하는데 유용함.
• 텍스트 검색, 자동 완성, 사전 구현 등에서 널리 사용됨.

Trie 구조

Trie 는 노드(node)와 간선(Edge) 로 구성된 트리임. 각 노드는 하나의 문자(character) 를 나타내며, 루트 노드부터 각 노드로의 경로는 하나의 문자열을 나타냄.

Trie 의 각 노드에는 다음과 같은 정보가 저장됨.

1. 자식 노드에 대한 포인터 또는 참조(Children)
   • 각 노드는 자식 노드에 대한 참조를 가짐. 자식 노드는 현재 노드에서 이어지는 다음 문자들을 나타냄.
2. 끝 표지(End of Word)
   • 일부 구현에서는 노드에 현재 노드까지의 경로가 유효한 단어의 끝인지 표시하는 플래그를 포함함.

주요 연산

1. Insert(삽입)
   • 문자열을 Trie 에 삽입할 때는 루트 노드에서 시작하여 문자열의 각 문자를 따라 내려가면서 노드를 추가함.
     만약 해당 문자가 이미 존재하는 노드에 있다면, 그 노드를 따라가고, 없다면 새 노드를 생성하여 연결함.
     마지막 문자 노드에 단어의 끝을 표시함.
2. Search(검색)
   • 특정 문자열이 Trie 에 존재하는지 검색할 때는 루트 노드에서 시작하여 문자열의 각 문자를 따라 내려감.
   • 문자열의 모든 문자를 따라가면서 노드가 존재하면 마지막 노드에서 단어의 끝 표시를 확인하여 존재 여부를 판단함.
3. Delete(삭제)
   • 문자열을 삭제할 때는 먼저 해당 문자열이 Trie 에 존재하는지 확인 후, 존재하면 노드를 역으로 탐색하면서 단어의 끝 표시를 제거하거나 불필요한 노드를 삭제함.
4. Autocomplete(자동 완성)
   • 특정 접두사로 시작하는 모든 단어를 찾기 위해서는 해당 접두사의 마지막 문자가 있는 노드로 이동한 후, 그 노드에서부터 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색) 을 통해 모든 자식 노드 경로를 탐색함.

장단점

장점

1. 빠른 검색 속도 : 문자열의 길이에 비례하여 검색이 가능하므로, 접두사 검색 및 단어 검색이 매우 빠름.
2. 공통 접두사 저장의 효율성 : 공통 접두사를 공유하는 문자열들이 하나의 경로를 공유하므로 저장 공간을 절약할 수 있음.

단점

1. 공간 복잡도 : 각 노드가 자식 노드에 대한 포인터를 여러 개 가지고 있으므로, 메모리 사용량이 많아 질 수 있음.
2. 구현의 복잡성 : Trie 구조를 구현하고 유지 관리하는 데 복잡할 수 있음

예시

"hello", "heaven", "heavy" 라는 단어를 저장한 Trie 의 예시임.

 

이 Trie 에서

• "he" 로 시작하는 단어들은 "hello", "hell", "heaven", "heavy" 임
• "hell" 로 시작하는 단어들은 "hello", "hell" 임