# 인덱스

### 인덱스(Index)

![](https://github.com/jmxx219/CS-Study/assets/74135929/45b08780-a61e-439f-877a-ad242c15042d)

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

\


**개념**

* 데이터베이스에서 컬럼(속성)을 기반으로 빠른 검색을 지원하기 위한 자료구조
* 특정 컬럼 값 기반으로 테이블 행에 대한 물리적인 위치를 찾아 매핑
* 테이블에 대한 보조 구조로써 생성되며, 원본 데이터와 별도로 관리
* 특정 컬럼에 인덱스 생성 시, 해당 컬럼의 데이터를 정렬 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장
* 컬럼 값, 물리적 주소를 (Key, value) 한 쌍으로 저장

\


**장점**

* 테이블의 검색 속도와 성능 향상
  * 전반적인 시스템 부하를 줄임
* 데이터들이 정렬된 형태를 가짐
  * Full Table Scan(특정 데이터 검색을 위해 테이블 전체 조건과 비교) 작업 불필요
  * ORDER BY, MIN/MAX 작업의 빠른 수행

\


**단점**

* 인덱스 관리를 위한 오버헤드가 발생
  * 원하는 값을 빠르게 탐색하기 위해 항상 정렬된 상태로 유지해야 한다.
    * 삽입(INSERT) : 새로운 데이터에 대한 인덱스 추가
    * 삭제(DELET) : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행
    * 수정(UPDATE) : 기존의 인덱스 사용않음 처리 및 갱신된 데이터의 인덱스 추가
* 데이터 잦은 수정 작업시 성능 저하
  * 인덱스 제거가 아닌 '사용하지 않음'처리 남겨둬 수정 작업이 많은 경우 데이터에 비해 과도하게 인덱스 커짐
* 인덱스를 관리하기 위해 DB의 약10%의 추가적인 저장공간이 필요
* 데이터의 수에 따라 풀스캔이 효율적일수 있다.
  * 1개의 데이터가 들어있는 테이블의 경우 인덱스를 이용하는 것보다 풀스캔이 효율적이다.

\
\


### 인덱스의 자료구조

인덱스를 구현하는 대표적인 자료구조로는 **해시 테이블(Hash Table)** 과 **B+Tree**가 있다

\


#### 해시 테이블(Hash Table)

Key와 Value를 한 쌍으로 데이터를 저장하는 자료구조

* (key, value) 쌍 표현
* key값을 이용해 대응되는 value값을 구함
* 평균적으로 O(1)의 빠른 시간에 데이터 탐색 (해시 충돌의 변수 존재)

\


**인덱스와 해시 테이블**

* (Key, value) = (컬럼의 값, 데이터의 위치)로 인덱스 구현
* 실제로 인덱스에서 잘 사용X
  * 해시 테이블은 등호(=)연산에 최적화
  * 데이터베이스에선 부등호(<,>) 연산이 자주 사용 됨
  * 해시 테이블 내 데이터들은 정렬되어있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내 찾을 수 없음

\


#### B+Tree

![](https://github.com/jmxx219/CS-Study/assets/74135929/ee063dd9-de5a-48ab-9998-4be120e3280d)\
기존의 B-Tree의 단점을 개선시킨 자료구조\


* leaf node에만 데이터 저장
  * 중간 node에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있음
  * leaf node끼리 LinkdedList로 연결
* leaf node가 아닌 node에는 자식 포인터만 저장

leaf node끼리 LinkdedList로 연결하여 부등호를 이용한 순차 검색 연산이 자주 발생하는 경우 root로 돌아가 leaf node를 재탐색하는 것이 아닌 다음 node를 탐색한다.

\
\


### 인덱스의 존재여부와 ORDER BY/GROUP BY 연산의 동작 과정

#### **ORDER BY**

* 결과 집합을 특정 열 기준으로 정렬 시 사용
* 정렬 작업은 정렬을 수행할 열의 값을 비교하고 필요에 따라 데이터를 재배열하는 것을 의미

\


* **인덱스 미존재** ( ORDER BY의 기준이 되는 열에 인덱스 없을 경우 )\
  \- 데이터베이스는 전체 테이블을 스캔하여 정렬 수행\
  \- 대량의 데이터에 대해 매우 비효율적

\


* **인덱스 존재**\
  \- 데이터베이스는 인덱스를 사용하여 정렬 작업 수행\
  \- 인덱스는 정렬된 순서로 데이터에 액세스할 수 있도록 도와주어 정렬 작업 성능 향상

\


#### **GROUP BY**

* 특정 열을 기준으로 데이터를 그룹화 시 사용
* 그룹화된 결과는 주로 집계 함수와 함께 사용되어 그룹별로 데이터 요약, 분석시 유용

\


* **인덱스 미존재** ( GROUP BY의 기준이 되는 열에 인덱스 없는 경우 )
  * 데이터베이스는 전체 테이블을 스캔하여 그룹화 수행
  * 대량의 데이터에 대해서는 성능 문제 일으킬 가능성 존재

\


* **인덱스 존재**
  * 데이터베이스는 인덱스를 사용하여 그룹화 작업 수행
  * 인덱스는 동일한 그룹 값들이 연속적으로 저장되어 있으므로, 그룹화 작업의 성능을 향상

\
\


### 기본키와 인덱스

**기본 키**\
: 데이터베이스 테이블에서 각 행을 고유하게 식별하기 위해 사용되는 **열 또는 열의 집합**

\


**외래 키**\
: 관계형 데이터베이스에서 한 테이블의 열이 다른 테이블의 기본키를 참조하는 경우 사용되는 열

* 참조 무결성을 유지하고 테이블 간의 관계 설정 시 사용

\


**인덱스**\
: 데이터베이스에서 데이터에 대한 검색 및 정렬을 향상시키기 위해 생성되는 **데이터 구조**

\


**<기본키와 인덱스>**

기본키는 인덱스가 될 수 있지만, 기본키가 반드시 인덱스인 것은 아니다. 하지만 일반적으로 기본키 열에는 인덱스가 자동으로 생성되어 기본키의 고유성과 검색성능을 보장하는데 사용된다.

\


**<외래키와 인덱스>**

외래키 관계를 사용해 테이블 간의 JOIN작업을 수행하거나 외래키 열을 검색하는 경우 인덱스를 활용해 검색성능을 향상시킬 수 있다. 따라서 외래키 열에는 인덱스를 생성하는 것이 좋으며, 일반적인 관례로 외래키 열에 인덱스를 생성한다.
