Database Index

데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조

동작 원리

• 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장
• 쿼리문에 인덱스 생성 컬럼을 WHERE 조건으로 거는 등, 작업을 할 경우 옵티마이저에서 판단하여 생성된 인덱스를 활용 가능
• 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식으로 동작하게 되어 검색 속도 향상
• 오름차순으로 정렬하기 때문에 정렬된 주소 체계

💡 옵티마이저 : 가장 효율적인 방법으로 SQL을 수행할 최적의 처리 경로를 생성해주는 DBMS의 핵심 엔진, 컴퓨터의 두뇌가 CPU인 것처럼, DBMS의 두뇌는 옵티마이저

인덱스의 장점

가장 큰 특징은 데이터들이 정렬되어 있다는 점

조건 검색 WHERE 절의 효율성

• 인덱스 테이블 스캔(Index Table Scan)시 정렬되어 있기 때문에 WHERE절에 맞는 데이터를 빠르게 찾아낼 수 있음

정렬 ORDER BY절의 효율성

• ORDER BY에 의한 정렬은, 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크I/O가 이루어짐
• 인덱스는 이미 정렬이 되어 있기 때문에 가져오기만 하면 됨

MIN,MAX의 효율적인 처리

• MIN값과 MAX값을 가져올 때, 이미 정렬되어 있기 때문에 레코드의 시작 값과 끝 값만 가져오면 됨

인덱스의 단점

정렬된 상태를 계속 유지시켜줘야 함

DML에 취약

• INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 변경이 될 경우 인덱스 테이블 내에 있는 값들을 다시 정렬해야 함
• 데이터의 추가 삭제를 원본 테이블, 인덱스 테이블 두 번 해야 하기 때문에 오버헤드 발생
• 때문에 검색 위주의 테이블에 인덱스 생성

데이터가 많을 때 효율적임

• 전체 데이터의 10~15%정도일 때, 가장 효율적
• 그 이상의 데이터를 처리할 때는 용량에 대한 문제도 고려해야 함

인덱스의 관리

• INSERT : 새로운 데이터에 대한 인덱스 추가
• DELETE : 삭제하는 데이터의 인덱스를 사용하지 않음 처리 진행
• UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신 된 데이터에 대해 인덱스 추가

인덱스의 자료구조

해시테이블(Hash Table)

• (Key,Value)로 데이터를 저장하는 자료구조
• 빠른 데이터 검색이 필요할 때 유용
• Key값을 이용해 고유한 Index 생성 후, 그 Index에 저장된 값을 꺼내오는 구조

• 해시 테이블 기반의 DB 인덱스는 (Key,Value)를 통해 Index와 해당 주소값을 매칭시키고, 해당 주소에 접근하여 데이터를 꺼내옴
• 시간 복잡도는O(1)
• 해시는 등호(=)연산에만 특화되어 있음
  • 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성
  • 이와 같은 특성에 의해 부등호 연산(>,<)이 자주 사용되는 데이터베이스 검색에서는 적합하지 않음

B+Tree

• 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조
• 모든 노드에 데이터를 저장했던 B-Tree와 다른 특성을 가지고 있음
  • 리프 노드(데이터 노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스 노드) 들은 데이터를 위한 인덱스 만을 가짐
  • 리프 노드들은 LinkedList로 연결되어 있음
  • 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 됨
• BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화 한 것
• 시간 복잡도는 O(log2N)