색인

• 데이터 홍수의 시대이다.
• 어마어마한 양의 데이터 홍수 속에서 자신에게 필요한 데이터를 찾는 일은 자료구조와 알고리즘의 핵심 역할 중 하나이다.
• 데이터를 잘 찾으려면 잘 저장해야 하는데, 이때 나중에 데이터를 잘 찾을 수 있도록 색인을 만드는 것이 중요하다.

레코드, 키와 색인의 관계

• 레코드
  • 개체에 대한 모든 정보가 들어 있다.
  • 사람 레코드라면,
    • 주민 번호, 이름, 집 주소, 직장 주소 등등이다.
    • 이들 각각의 정보를 나타내는 부분을 필드라고 한다.
• 색인
  • 개체의 레코드를 검색하기 위한 것
  • 색인에 레코드를 다 저장한다면 -> 데이터베이스
  • 색인은 해당 레코드를 대표할 수 있는 필드로 만든다.

색인을 통해 어떤 레코드에 접근하기 위해서는
그 레코드의 키와 레코드가 저장된 위치에 관한 정보가 있으면 된다.

효율적인 색인

• 이진 검색 트리
  • 배열로 만든 색인보다 개선된 방법
  • 평균 Θ(logn) 시간에 검색, 삽입, 삭제를 할 수 있는 자료구조이다.

추상데이터 타입

색인에 키 x를 삽입한다.
색인에서 키 X를 검색한다.
색인에서 키 X를 삭제한다.
색인이 비어 있는지 확인한다.
색인을 깨끗이 비운다.