📙 인덱스란
추가적인 쓰기 작업과 저장 공간을 활용하여 DB 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
만약 인덱스를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. Full Scan은 전체를 비교하여 탐색하기 때문에 처리 속도가 떨어진다.
인덱스의 장단점
장점
1. 검색 대상 레코드의 범위를 줄여 검색 속도를 빠르게 할 수 있다.
2. 중복 데이터를 방지하거나 특정 컬럼의 유일성을 보장할 수 있다.
3. ORDER BY 절과 GROUP BY 절, WHERE 절 등이 사용되는 작업이 더욱 효율적으로 처리된다.
4. 전반적인 시스템의 부하를 줄일 수 있다.
단점
1. 인덱스를 관리하기 위해 추가적인 저장 공간이 필요하다.
2. CREATE(삽입), DELETE(삭제), UPDATE(수정) 작업 시에도 인덱스를 업데이트해야 하므로 성능 저하가 발생할 수 있다.
3. 한 페이지를 동시에 수정할 수 있는 병행성이 줄어든다.
인덱스의 관리
인덱스는 항상 최신 데이터를 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 따라서 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해줘야 한다. (그에 따른 오버헤드 발생.)
- INSERT : 새로운 데이터에 대한 인덱스를 추가.
- UPDATE : 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가.
- DELETE : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행.
인덱스를 사용하는 경우
-
대량의 데이터를 검색하는 경우
-
정렬된 결과를 출력하는 경우
-
조인 연산을 수행하는 경우에는 인덱스를 사용하여 연산 속도를 향상시킬 수 있다. 인덱스를 생성하여 조인 대상 테이블의 데이터를 빠르게 검색하는 것이 좋다.
-
유니크한 값을 가져오는 경우
-
검색 빈도가 높은 경우
인덱스의 자료구조
[해시 테이블]
키와 해시 값 쌍으로 이루어진 자료구조이다. 상당히 빠른 검색이 가능하다. (O(1)의 시간복잡도를 가지고 있다.)
해시 테이블의 검색 방식은 키를 해시 함수를 사용하여 해시 값으로 변환한 후, 해당 해시 값에 해당하는 값을 찾아서 검색한다. 해시 테이블은 검색 속도가 매우 빠르지만, 데이터의 분포에 따라 충돌이 발생할 수 있다. 따라서 충돌을 해결하기 위한 방법이 필요하다.
[B-Tree]
DB에서 가장 널리 사용되는 인덱스 자료구조 중 하나이다. (O(logN)의 시간 복잡도를 가지고 있다.)
균형 잡힌 이진 검색 트리로 DB에서 검색 속도를 높이기 위해 사용된다.
B-Tree의 각 노드 내 데이터들은 항상 정렬된 상태인 것이 특징이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. (자식 노드의 개수는 n+1개)
또한, 한 노드에서 여러 개의 키를 가질 수 있고, 키에 해당하는 데이터도 함께 갖고 있다.
[B+Tree]
균형 잡힌 이진 검색 트리이다. B+Tree는 B-Tree에 비해 더 많은 키를 가질 수 있다.
B+Tree는 B-Tree와 달리 내부 노드(Internal node)와 단말 노드(Leaf node)로 구분된다. B+Tree의 모든 데이터는 단말 노드에서만 저장되며, 내부 노드에는 검색을 위한 인덱스만 저장된다.
모든 리프 노드가 연결 리스트로 연결되어 있으며, 순차적으로 저장되어 있다. 이러한 특징으로 인해 범위 검색(Range Search)이나 순차 검색(Sequential Search)에 효율적이다.
Reference
🔗 https://ittrue.tistory.com/331
🔗 https://mangkyu.tistory.com/96
