인덱스(Index)

📌 인덱스란?

 

 

만약 다음과 같은 데이터베이스에서 age가 23인 사원을 찾아야 한다면 컴퓨터는 조건에 맞는 값을 찾을 때까지 검색을
계속할 것이다. 그런데 만약 데이터가 1억 개가 된다면 해당 데이터를 찾기 위해 오랜 시간이 걸리게 된다. 그래서 인덱스를
사용하여 타깃에 대한 빠른 접근을 도와준다.

 

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조를 말한다.

 

📌 인덱스 구조

 

우리가 데이터를 찾을 때 단순히 값을 물어보는 것이 아니라 내가 찾는 값이 어떤 값보다 큰지 작은지 물어보면서 접근하는 것이 더 유리할 것이다. 예를 들어, 1에서 100까지 값이 있을 때 55라는 값을 찾기 위해 50보다 큰지 작은 지부터 물어보면서
접근하는 것이다. 이를 위해서 전제되어야 할 것은 데이터 집합이 정렬되어 있어야 한다는 것이다.

 

 

이렇게 정렬해 놓은 컬럼을 인덱스라고 한다.

 

🔎 Hash Table

 

해시 테이블은 데이터 요소의 주소나 인덱스 값이 해시 함수에 의해 생성되는 데이터 구조다. 즉, 해시 테이블은 키와 값 쌍을
저장하고, 키를 통해 값을 찾아가며 키는 해싱 함수를 통해 생성된다. 그리고 해당 키 값 자체가 데이터를 저장하는 배열의
인덱스가 된다. 따라서, 데이터 요소의 검색 및 삽입 기능이 훨씬 빨라진다.

 

해시 테이블의 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원한다. 하지만 데이터베이스 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 조금이라도 달라지면 완전히
다른 해시 값(인덱스)을 생성한다. 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색에 적합하지
않다.

 

https://applepick.tistory.com/155

 

🔎 Tree

 

실제 데이터베이스는 인덱스를 저장할 때 Tree 형태로 저장한다.

 

Tree 자료구조

 

이렇게 데이터를 정렬된 상태에서 작은 값은 왼쪽으로 큰 값은 오른쪽으로 배치하여 조사 대상을 반씩 줄여가는 방식을
이진 검색(Binary Search)이라고 하며, 이러한 방식으로 만든 트리를 이진 검색 트리(Binary Search Tree)라고 한다.

 

🔎 B-Tree

 

위 숫자들을 노드라고 하는데, 해당 노드에 데이터가 2개 이상 들어간다면 성능이 더욱 향상될 것이다. 이처럼 각 노드는 2개
이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된 트리를 B-Tree라고 한다.

 

B-Tree 자료구조

 

이렇게 하면 한 번에 반씩 잘라 나가는 것이 아니라, 1/3, 1/4 씩 잘라서 검색할 수 있다. 그 결과, 위의 이진 탐색
트리처럼 2번의 이동으로 7보다 더 큰 숫자까지 검색할 수 있다.

 

🔎 B+ Tree

 

데이터베이스 인덱스를 위해 B-Tree를 개선시킨 자료구조로 아래와 같은 특징을 가진다.

 

• 리프노드(데이터 노드)만 인덱스와 함께 데이터를 갖고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(key)만을 갖는다.
• 리프노드들은 연결 리스트로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

 

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 그래서 B-Tree의 리프노드들을
연결 리스트로 연결하여 순차 검색을 용이하게 하는 등 B-Tree를 인덱스에 맞게 최적화하였다.

 

 

이처럼 리프노드 외 노드는 데이터를 찾기 위한 가이드라인만 제공하고, 리프노드끼리 연결 리스트로 연결되어 있기 때문에
범위 검색이 용이하다.

 

📌 정리

 

인덱스가 없다면 최악의 경우 모든 행을 다 뒤져서 값을 찾아온다.

 

인덱스가 있다면 인덱스부터 찾는 값을 찾은 뒤 그 인덱스와 연결된 원래 테이블 행을 가져온다. 따라서, 데이터베이스 검색
속도가 향상되는 효과를 볼 수 있다.

 

하지만 단점도 존재한다. 인덱스는 컬럼을 복제해서 저장해 두는 개념이기 때문에 그만큼 데이터베이스 용량을 차지한다.
그래서 검색 작업이 필요 없는 데이터에 대해서는 인덱스를 만들 필요가 없다.

 

또 다른 단점은 기존 테이블에 삽입, 수정, 삭제를 하게 되면 인덱스에도 동일하게 반영해야 한다. 이러한 추가 쿼리가
잦아진다면 오히려 성능 하락이 있을 수 있다.

 

Primary key는 자동으로 정렬되어 있기 때문에 굳이 인덱스를 만들어 둘 필요는 없다. 그리고 이러한 PK를 Clustered index라고 한다.

 

References:

https://applepick.tistory.com/155

[index] B+-Tree, Hash Table

 

https://mangkyu.tistory.com/96

[Database] 인덱스(index)란?

 

https://www.youtube.com/watch?v=iNvYsGKelYs