인덱스와 그 작동원리

Index

데이터베이스에서 검색 속도를 향상하기 위해 사용되는 자료구조입니다.

데이터베이스 테이블에 대한 인덱스는 특정 칼럼의 값을 미리 정렬하여 검색 및 정렬 작업을 빠르게 수행할 수 있도록 도와줍니다. 인덱스를 사용하면 데이터베이스 관리 시스템은 전체 테이블을 스캔하지 않고도 원하는 데이터를 빠르게 찾을 수 있습니다.

[출처]: https://mangkyu.tistory.com/96

장점

1. 데이터 검색 속도 향상 : 인덱스를 사용하면 특정 칼럼의 값을 미리 정렬하여 검색 작업을 빠르게 수행할 수 있습니다. 인덱스를 통해 검색 조건에 부합하는 데이터를 빠르게 찾아낼 수 있습니다.
2. 정렬 작업 개선 : 인덱스를 사용하면 데이터베이스 엔진은 정렬 작업을 더 효율적으로 수행할 수 있습니다. ORDER BY절과 같은 정렬 연산에서도 성능 향상을 가져올 수 있습니다.
3. 중복 데이터 제어 : 인덱스를 통해 특정 칼럼의 중복된 값들을 제어하고 관리할 수 있습니다. 이로써 데이터 일관성을 유지할 수 있습니다.
4. 빠른 데이터 접근 : 인덱스를 사용하면 데이터베이스 시스템은 실제 데이터를 찾기 위해 더 적은 양의 데이터를 접근하므로 I/O비용이 줄어들어 빠른 데이터 접근을 가능하게 합니다.

단점

1. 공간 사용 : 인덱스는 추가적인 저장 공간을 필요로 합니다. 테이블 크기와 상관없이 인덱스가 크기를 차지하게 되므로, 인덱스가 많아지면 디스크 공간 사용량이 증가할 수 있습니다.
2. 성능 저하 : 인덱스는 데이터의 변경 작업 시에도 업데이트되어야 합니다. 인덱스 업데이트 작업은 데이터 변경 작업의 부담을 증가시킬 수 있습니다. 또한, 인덱스의 잘못된 설계는 성능 저하를 초래할 수 있습니다.
3. 인덱스 선택의 어려움 : 어떤 칼럼을 인덱스로 선택할지 결정하는 것은 어려운 과정입니다. 너무 많은 인덱스를 생성하면 업데이트 작업에 부하가 생기고, 너무 적은 인덱스를 생성하면 검색 성능이 저하될 수 있습니다.
4. 인덱스 유지 비용 : 인덱스를 생성하고 유지하는 비용이 발생합니다. 데이터 변경 시에 인덱스도 업데이트되어야 하며, 이로 인해 일관성 유지와 성능 향상 사이의 균형을 유지해야 합니다.

Index 작동 원리

1. 인덱스 생성 : 인덱스를 사용하려면 먼저 테이블에 대한 인덱스를 생성해야 합니다. 이때 인덱스가 생성될 컬럼을 선택합니다.
2. 값 정렬 : 인덱스가 생성될 칼럼의 값들을 정렬합니다. 이 정렬은 해당 컬럼의 값을 기준으로 오름차순 또는 내림차순으로 정렬됩니다.
3. 인덱스 트리 구조 : 대부분의 DBMS에서는 B-트리 또는 B+트리와 같은 트리 구조를 사용하여 인덱스를 구성합니다.. 이 트리 구조는 각 노드가 여러 개의 자식 노드를 가지며, 효율적인 데이터 검색을 위해 데이터를 분할하고 조직화하는 데 사용됩니다.
4. 검색 및 조작 : 데이터를 검색하거나 조작할 때, DBMS는 먼저 인덱스를 확인하여 검색 조건과 일치하는 데이터를 빠르게 찾습니다. 이때 인덱스 트리를 탐색하여 적절한 위치로 이동하면서 검색 조건에 부합하는 데이터를 찾게 됩니다.
5. 테이블 접근 : 인덱스를 통해 식별된 데이터의 위치를 찾은 후, DBMS는 해당 데이터가 저장된 실제 테이블로 접근하여 데이터를 가져옵니다. 이때 인덱스를 사용하지 않는 경우보다 훨씬 적은 양의 데이터를 접근해야 하므로 성능이 향상됩니다.
6. 인덱스 업데이트 : 데이터가 추가, 수정 또는 삭제될 때마다 인덱스도 업데이트되어야 합니다. 이때 인덱스 업데이트는 데이터의 일관성과 성능을 유지하기 위해 중요한 작업입니다.

인덱스는 모든 상황에서 성능 향상을 보장하지는 않습니다. 인덱스를 많이 사용하면 데이터 삽입, 수정, 삭제 작업의 성능이 저하될 수 있습니다. 또한 작은 테이블이나 빈번한 변경이 없는 테이블의 경우에는 인덱스가 오히려 부가적인 부하를 일으킬 수 있습니다. 따라서 인덱스를 설계할 때에는 데이터베이스의 크기, 사용 패턴, 성능 요구 사항 등을 고려하여 적절한 익덱스 전략을 선택하는 것이 중요합니다.

Index 구조

B-트리

데이터 베이스에서 가장 흔하게 사용되는 인덱스 구조 중 하나입니다. 이진트리를 기반으로 한 구조로, 균형을 유지하여 효율적인 검색 및 삽입, 삭제 작업을 지원합니다.

B-트리 특징

• 균형 트리 구조 : B-트리는 균형 트리로써, 루트 노드에서 리프 노드까지의 경로 길이가 동일합니다. 이로 인해 검색 작업 시 빠른 성능을 유지할 수 있습니다.
• 다수의 키와 자식 노드 : 각 노드는 여러 개의 해당 키에 연결된 자식 노드를 가질 수 있습니다. 이로써 한 노드가 다수의 키를 포함하고 효율적인 데이터 분할이 가능해집니다.
• 정렬된 키 : 각 노드 내의 키는 정렬된 상태를 유지합니다. 이는 검색 및 정렬 작업의 효율성을 향상시킵니다.
• 분할과 병합 작업 : 노드에 새로운 키가 삽입되거나 삭제될 때, B-트리는 자동으로 노드를 분할하거나 병합하여 균형을 유지합니다.
• 데이터 삽입 및 삭제 작업 : B-트리는 데이터의 삽입 및 삭제 작업을 효육적으로 수행할 수 있습니다. 분할과 병합 작업을 통해 균형을 조절하면서도 상대적으로 높은 성능을 유지합니다.
• 데이터베이스 인덱스 구성 : 데이터베이스에서는 테이블의 인덱스를 B-트리를 기반으로 구성하여 데이터 검색을 빠르게 할 수 있습니다.

B+트리

B-트리의 파생된 구조로 B+트리는 다양한 특징을 가지고 있어 데이터 베이스 시스템에서 효율적인 데이터 관리를 가능하게 합니다.

• 리프 노드에 데이터 저장 : B+ 트리는 데이터를 리프 노드에 저장합니다. 내부 노드에는 키만 저장되고, 실제 데이터는 리프 노드에 위치합니다. 이로써 범위 검색 시 데이터를 연속적으로 찾을 수 있어 디스크 I/O를 최소화하고 순차적 접근을 촉진합니다.
• 리프노드 간 연결 : B+트리의 리프 노드는 연결 리스트 형태로 연결됩니다. 이 연결 리스트를 통해 순차적 검색이나 범위 검색이 더 효율적으로 수행될 수 있습니다.
• 키 중복 허용 : 리프 노드에서는 키 중복을 허용합니다. 같은 키를 가진 데이터들이 모두 정렬되어 저장되므로 범위 검색을 효율적으로 수행할 수 있습니다.
• 내부 노드의 키 저장 : 내부 노드에는 키만 저장되며, 이 키는 하위 노드를 분리하는 역할을 합니다.
• 균형 유지 : B+트리는 높이 균형을 유지하여 효율적인 검색 작업을 보장합니다. 리프 노드까지의 경로 길이가 일정하며, 내부 노드의 분할 작업을 통해 균형을 조절합니다.
• 검색 및 삽입/삭제 성능 : B+트리는 평균적으로 O(log N) 시간에 검색 및 삽입/삭제 작업을 수행할 수 있습니다. 이는 대량의 데이터를 빠르게 처리하는 데에 매우 유용합니다.
• 인덱스 업데이트 부담 완화 : B+트리는 데이터의 삽입 및 삭제 작업에 유리한 특징을 가지고 있어, 인덱스 업데이트 시의 부담을 완화할 수 있습니다.

[출처]: Why and when do you need to rebuild indexes in SQL databases for performance? - Quora