[데이터베이스] 인덱스(index)
데이터베이스에는 인덱스(index)라는 개념이 있다.
배열에 사용되는 인덱스와 데이터베이스의 인덱스는 같은 이름을 사용하지만 그 의미와 역할은 다소 다르다.
하지만, 둘다 데이터의 위치를 참조한다는 공통점을 가지고 있다.
배열에서의 index
배열에서의 인덱스는 알다시피 배열 내에서 특정 요소의 위치를 나타내는 정수이다.
인덱스를 통해 우리는 배열에서 빠르게 데이터에 접근하고 수정하는 것이 가능하다.
데이터베이스에서의 index
데이터베이스에서 인덱스는 배열의 그것과 사뭇다르다.
결론부터 말하자면 인덱스는 테이블 내 특정 열에 대한 검색 속도를 높이기 위해 사용되는 자료 구조이자 데이터베이스의 기능을 의미한다.
예를 들어, 다음과 같은 데이터베이스에서 23살에 해당하는 사람의 데이터를 알고 싶다면 하나하나 알아보는 방법이 있다.
하지만 이 방법의 경우 O(N)의 시간복잡도를 요하기 때문에 이분 탐색을 이용하면 더 빠르게 검색할 수 있을 것이다.
예시에서는 데이터의 수가 많지 않기에 상관없어보이지만, 데이터의 수가 아주 많다면 나이가 20살보다 많은지, 30살보다 적은지, 이런식으로 행(Column)을 반씩 잘라가며 검색을 진행하는 것이 훨씬 효율적일것이다.
하지만, 이러한 이분탐색을 진행하기 위해서는 전제조건이 있다.
행의 데이터를 정렬해야한다는 것이다. 그래야 행을 반씩 잘라가며 검색을 진행할 수 있을 것이다.
그리고 이렇게 검색을 빠르게 진행하고 싶은 열을 복사하여 정렬해놓은 것을 인덱스(index)라고 부른다.
인덱스의 구현 방식
인덱스가 정렬해놓은 특정한 행 사본이고 이분 탐색을 이용한다면 인덱스가 트리 형태로 구현되어있다는 것을 어렵지 않게 추론할 수 있다.
그리고 실제 인덱스를 만들때 성능 향상을 위해 B-Tree 혹은 B+Tree와 같은 자료구조를 기반으로 구현한다.
B-Tree
우선 B-Tree는 이진트리와 유사한 형태이나 각 노드마다 노드를 두개 이상, 그리고 자식노드를 둘이상 가질 수 있는 트리구조를 의미한다. 균형잡힌 트리이며, 기본적인 트리에 비해 더 적은 연산횟수로 원하는 값을 찾아낼 수 있으며, 탐색에 있어 O(logN)을 보장한다.
B+Tree
이전에 B-Tree보다 성능적으로 더욱 향상된 것이 이 B+Tree라고 할 수 있다.
B-Tree와 가장 큰 차이점은 B+Tree에서는 리프노드에만 데이터를 저장하며 다른 노드는 포인터, 가이드의 역할만을 수행한다는 것이다.
또한, 리프노드끼리는 연결 리스트로 연결이 되어있다는 특징도 있다.
이렇게 데이트를 배치함으로서 범위 검색이 매우 유리해진다는 장점이 있다.
예를 들어, 7~9까지의 숫자를 탐색하고 싶다면 B-Tree에서는 리프노드까지 내려갔다가 다시 올라오는 작업을 수행해야하는 반면, B+Tree에서는 리프노드에 도착후, 화살표를 타고 다음 노드로 이동만 하면 되기에 훨씬 쉽다.
해시테이블을 이용한 구현
인덱스를 구현하기 위해 해시테이블을 사용할수도 있다.
이 경우, 값을 변경하여 해시맵 형태로 저장하며 최악의 경우 (N)의 시간 복잡도를 갖지만, 대부분의 상황에서 (1)의 시간복잡도를 가진다.
하지만 해시테이블을 통한 구현은 특정 상황에서는 매우 효율적일 수 있지만, 그만큼 제한도 있다.
예를 들어, 정확한 값 검색이 중요한 서비스의 경우 해시테이블이 효과적일 수 있다.
해시 테이블은 정확한 값 검색에 매우 효율적이기에,
SELECT * FROM users WHERE user_id = 1234; 와 같은 쿼리에서 해시 인덱스는 빠르게 작동할 것이다.
또한, 읽기 위주의 작업이 많은 환경이 많고, 빠르게 데이터를 읽어와야 하는 사용자 인증 시스템, 캐싱 시스템과 같은 경우, 해시 인덱스가 유용할 수 있다. 즉, 삽입, 삭제, 수정 작업이 많지 않은 환경에서 유리하는 것이다.
CREATE INDEX idx_user_id ON users USING HASH (user_id);
- 사용자 로그인 시 ID로 빠르게 검색가능
SELECT * FROM users WHERE user_id = 1234;
해시 테이블 기반 인덱스를 피해야 하는 경우
반면, 범위 검색이 필요한 경우, 정렬된 결과가 필요한 경우, 높은 삽입과 삭제 빈도를 가지는 환경에서는 해시 인덱스를 피해야한다.
왜냐하면, 기본적으로 해시 테이블은 범위 검색에 적합하지 않으며, 해시 테이블을 데이터를 정렬된 순서로 유지하지 않기 때문이다.
따라서 ORDER BY나 GROUP BY와 같은 쿼리에서 해시 인덱스는 적합하지 않다.
또한, 잦은 삭제와 삽입이 발생할시 해시 충돌과 해시 재해싱이 발생할 수 있으며 이 경우 성능 하락으로 이어지게 된다.
인덱스의 단점
이렇듯, 인덱스는 그저 좋아보이기만 할 수 있지만 그렇지 않다.
성능이 뛰어나다는 것은 다른 관점에서는 매우 비효율적이거나 떨어지는 성능을 보일 수도 있다는 것이다.
인덱스는 조회 성능을 높이고 그 대가로 삽입 / 삭제 / 수정 성능을 어느정도 포기한다.
삽입/삭제/수정 성능이 감소하는 이유
일단 인덱스를 관리함에 있어 별도의 인덱스가 페이지가 필요하다.
그리고 삽입, 삭제, 수정과 같은 작업을 테이블에서 행한다면 이로 인한 변경점을 인덱스에도 똑같이 적용해줘야할 것이다.
그렇다는 것은 삽입, 삭제, 수정 시 추가적인 연산이 필요하다는 것이다.
삭제 시의 인덱스 동작
데이터베이스에서 데이터를 삭제할 때, 인덱스에서는 실제로 데이터를 즉시 제거하지 않고 "사용하지 않는" 상태로 표시합니다.
이를 통해 실제로 데이터를 삭제하는 것보다 빠르고 효율적으로 해당 동작을 수행할 수 있는 것이다. 또한, 인덱스를 유지하는 동안 다른 트랜잭션과의 충돌을 피하기 위함이기도 하다.
따라서, 테이블에서 데이터를 삭제했더라도 인덱스 페이지에는 여전히 데이터가 존재할 수 있다.
그리고 이 삭제 표시된 데이터는 이후에 인덱스를 정리(재구성)하는 과정에서 실제로 제거된다.
수정 시의 인덱스 동작
데이터베이스에서 데이터를 수정할 때, 내부적으로는 삭제 이후 삽입과정이 일어난다.
이렇게 하는 이유는 대부분의 인덱스 구조, 특히 B-트리와 같은 구조에서는 데이터를 수정하는 것보다 삭제하고 새로 삽입하는 것이 더 간단하고 효율적이기 때문이다.
수정 시에도 삭제와 동일하게 삭제 표시가 사용되며, 이후에 새로운 데이터가 삽입된다.
인덱스가 필요한 경우 & 필요없는 경우
인덱스는 데이터 타입에도 영향을 받으며 중복이 적고 가질수 있는 값의 범위가 큰 경우 유리하다.
중복이 높다는 것은 해당 값을 가진 레코드가 많다는 것이고 그만큼의 데이터를 읽어야 하기 때문에 인덱스의 제 성능을 이끌어 낼 수 없다.
또한, 검색 기능이 필요하지 않은 경우, 인덱스는 필요없을 수 있고, Primary-Key로 설정되어 있는 행은 기본적으로 정렬이 되어 있기 때문에 이 경우에도 인덱스는 필요하지 않을 수 있다.