검색이 빠른 자료구조

O(1) > O(log n) > O (n) > O(n log n) > O(n^2) > O(n^3) > O(2^n) > O(n!)

HashMap

• 단건 검색 시간 복잡도 : O(1)
• 범위 탐색 시간 복잡도 : O(N)
• 전방 일치 탐색 불가 ex) like 'AB%'

List

• 정렬되지 않은 리스트 탐색 시간 복잡도 : O(N)
• 정렬된 리스트 탐색 시간 복잡도 : O(logN)
• 정렬 되지 않은 리스트 정렬 시간 복잡도 : O(N) ~ O(N * logN)
• 삽입/삭제 비용이 매우 높다

Tree

• 트리 높이에 따라 시간 복잡도 결정
• 트리의 높이를 최소화 하는 것이 중요!
• 한쪽으로 노드가 치우치지 않도록 균형을 잡아 주는 트리 사용
  • ex) Red-Black Tree, B+Tree

B+Tree

• 삽입/삭제시 항상 균형을 이룸
• 하나의 노드가 여러 개의 자식 노드를 가질 수 있음
• 리프노드에만 데이터 존재
  • 연속적인 데이터 접근 시 유리