인덱스
데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조
테이블의 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장
인덱스의 장단점
장점
- 테이블을 검색하는 속도와 성능이 향상되며 시스템의 전반적은 부하를 줄일 수 있다.
- 조회할때 인덱스를 이용하면 데이터가 정렬되어 있기에 조건에 맞는 데이터를 찾을 수 있다.
단점
- 인덱스를 관리하기 위한 추가 작업이 필요
- 추가 저장 공간 필요
- 잘못 사용하는 경우 오히려 검색 성능 저하
사용하면 좋을 때
- 규모가 큰 테이블
- 삽입, 삭제, 수정의 작업이 적은 곳
- 데이터의 중복도가 낮은 곳
인덱스의 자료구조
1. Direct Address Table
키 값을 주소로 사용하는 테이블
한계점
- 최대 키 값을 알고 있어야한다.
- 최대 값이 작을 때 효율적
- 키 값들이 골구로 분포되어 있지 않다면 메모리 낭비가 심해진다
2. Hash Table
해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조
문제점
- 해시 테이블의 크기 대비 키 개수가 많을때 적재율이 1초과하면 충돌이 발생
충돌이 발생하지 않는다면 조회, 삭제, 수정, 삽입 모두 O(1)에 수행하지만 충돌이 발생할 경우 O(n)만큼 걸린다.
3. B-Tree
탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tree의 일종
모든 leaf node가 같은 level로 유지되도록 자동으로 밸런스를 맞춰준다.
조건
-
node의 key의 수가 k개라면, 자식 node의 수는 k+1개이다.
-
node의 key는 반드시 정렬된 상태여야 한다.
-
자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 나뉘게 된다.
-
root node는 항상 2개 이상의 자식 node를 갖는다.
-
모든 leaf node들은 같은 level에 있어야 한다.
4. B+Tree
B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.
- 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다
- leaf node끼리는 LinkedList로 연결되어 있다.
- leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.
장점
- leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리 확보가 가능
- 하나의 node에 더많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도가 빠르다
- Full scan할 경우 B-tree는 모든 노드를 검색 해야하는 반면 LinkedList로 연결되어 있기 때문에 O(n)을 갖는다.
단점
- 특정 key에 접근하기 위해서 leaf node까지 가야 하는 단점이 있다.
B-Tree 대신 B+Tree를 사용 하는 이유는 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적이다
5. 레드블랙 트리 (RB Tree)
자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.
- 자가균형 이진 트리
실시간 처리와 같은 실행 시간이 중요한 경우에 유용하며 실행 시간을 보장하는 다른 자료구조를 만들 때에도 사용된다.
