Index란?
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.
이 비유를 그대로 가져와서 인덱스를 살펴본다면 데이터는 책의 내용이고 데이터가 저장된 레코드의 주소는 인덱스 목록에 있는 페이지 번호가 될 것이다.
DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져 오려면 시간이 오래 걸린다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것이다.
인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 그러한 이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.
// KledYu이라는 이름을 업데이트 해주기 위해서는 Kled을 조회해야 한다.
UPDATE USER SET NAME = 'KledYu' WHERE NAME = 'Kled';만약 index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. Full Scan은 전체를 비교하여 탐색하기 때문에 처리 속도가 떨어진다.
인덱스(index)의 장점과 단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
Index 자료구조
그렇다면 DBMS 는 인덱스를 어떻게 관리하고 있는가?
B-Tree 인덱스 알고리즘
-
노드 하나에 여러 데이터가 저장될 수 있다.
-
각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다.
-
각 노드에는 여러 개의 Key를 가지고 있고 각 Key에 대응하는 Data도 함께 갖고 있다.
-
같은 노드 상에서 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스의 접근한다.
항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.B+-Tree 인덱스 알고리즘
-
Leaf Node만 인덱스와 함께 데이터를 가지고 있고, 나머지 노드(Inner Node)들은 데이터를 위한 인덱스(Key)만을 갖는다.
-
Leaf Node들은 LinkedList로 연결되어 있다.
B-Tree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등
칼럼의 값을 변형하지 않고 B-Tree를 인덱스에 맞게 최적화하였다.
(물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 B-Tree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)Hash Table 인덱스 알고리즘
사실 탐색 시간이 빠른 것으로 인덱스 자료 구조를 선택한다면, 시간복잡도가 O(logN)인 다른 자료 구조를 사용하거나 시간복잡도가 O(1)인 해시 테이블을 사용하는 것이 더 빠를 수 있다.
하지만 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적이다
데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적일 것 같은데? SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. Hash Table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 Hash Table이 적합하지 않다.
출처: https://mangkyu.tistory.com/96 [MangKyu's Diary:티스토리]
