1. 인덱스
인덱스는 테이블에 붙여진 색인이다.
- 역할: 검색속도 향상 (검색: SELECT 명령에 WHERE 구로 조건을 지정하고 그에 일치하는 행을 찾는 일련의 과정)
- 구조: 검색 시에 쓰이는 키워드와 대응하는 데이터 행의 장소 저장
테이블과는 별개로 독립된 데이터베이스 객체로 작성된다. 인덱스는 테이블에 의존하는 객체로써 데이터베이스에서 테이블 삭제 시 인덱스도 같이 삭제된다.
2. 검색에 사용하는 알고리즘
데이터베이스의 인덱스에 쓰이는 대표적인 검색 알고리즘으로는 이진 탐색이 된다. 이때 이진탐색에서 검색하기 쉬운 구조로 한 것이 이진트리이다.
- 풀 테이블 스캔(full table scan)
인덱스 지정되지 않은 테이블 검색 시 풀 테이블 스캔 방법 사용
- 테이블에 지정된 모든 값을 처음부터 차례로 조사
- 단순
- 1000개 -> 1000번 값 비교
- 이진 탐색 (binary search)
차례로 나열된 집합에 대해 유효한 검색 방법
- 집합을 반으로 나누어 조사
실제 데이터베이스에는 수만, 수천만 건의 행이 있으므로 풀 테이블 스캔 시 데이터 수에 비례해 비교횟수도 늘어난다. 그에 비해 이진 탐색은 데이터 수가 배가 되어도 비교횟수는 1회 밖에 늘어나지 않는다.
대량의 데이터 검색 시 이진 탐색이 빠르다.
- 이진 트리(binary tree)
이진 탐색은 고속이지만 데이터가 정렬되어 있어야 한다. 하지만 테이블의 행을 언제나 정렬된 상태로 두는 것은 힘들다.
일반적으로 테이블에 인덱스 작성시 테이블 데이터와 별개로 인덱스용 데이터가 저장장치에 만들어진다. 이때 이진 트리라는 데이터 구조로 작성된다.
트리는 노드라는 요소로 구성되며 각 노드는 두개의 가지로 나눠진다. 노드의 왼쪽 가지는 작은 값으로, 오른쪽 가지는 큰 값으로 나뉘어져 있다.
검색은 이진 트리의 가지를 더듬어 가며 행해진다. 가운데 값부터 검색하여 작은 경우 왼쪽 가지를 큰 경우 오른쪽 가지를 탐색하며 반복한다.
3. 유일성
이진 트리의 노드는 중복되는 값을 가질 수 없다. 즉, 키에 대하여 유일성을 가지게 할 경우에만 유용하다. 그래서 기본키 제약은 이진 트리로 인덱스를 작성하는 데이터베이스가 많다.
이진 트리에는 중복하는 값을 등록할 수 없다.
