Searching

Keys

• key는 데이터를 구분하기 위한 요소

구분

1. Super Key

• 표에서 행을 구분할 수 있는 속성 값

2. Candidate Key

• 단일하며 단순성을 충족하는 Super Key

3. Primary Key

• Candidate Key 중에서 대표성을 가진 것을 선택
• null일 수 없고, 중복될 수 없으며 안정적이어야 함

4. Alternate Key

• Candidate Key 중에서 Primary Key로 선택되지 않은 나머지

Map

• 검색을 위한 자료 구조
• key를 활용해 빨리 자료를 탐색할 수 있도록 설계됨
• key - value 쌍을 통해 빠르게 값을 찾을 수 있음
• 삽입, 검색, 삭제 기능을 가지는 것이 가장 중요
• Array, Binary Search Tree 등을 통해서도 구현할 수 있지만 Hashing을 통해 구현하는 것이 굉장히 빠른 검색 속도를 가짐
• 정렬되지 않은 배열을 사용할 경우 O(n), 정렬된 배열은 O(log₂n)의 시간 복잡도를 가짐
• 균형잡힌 이진 검색 트리 또한 O(log₂n)의 시간 복잡도를 가짐
• 그러나 Hash를 통하면 O(1)의 시간 복잡도로 검색 기능을 구현 가능. 이 때문에 데이터가 많을수록 Hash를 사용하는 것이 유리