[Database] Index가 무엇인지 설명해보세요.

이미지 출처: https://user-images.githubusercontent.com/38887077/76482821-4ec64780-6450-11ea-862e-da506f5cdae2.png

Index

책에서 인덱스는 일반적으로 책의 끝에 위치하며, 키워드나 용어를 알파벳 순으로 나열하고 그 용어가 책에서 어디에서 논의되었는지에 대한 페이지 번호를 함께 제공합니다. 이는 독자들이 특정 정보를 빠르게 찾을 수 있도록 도와줍니다.

 

책의 인덱스가 특정 주제나 키워드에 대한 정보를 빠르게 찾는데 도움이 되는 것처럼, Index(인덱스)는 데이터베이스 엔진이 테이블 내의 특정 데이터를 더 빠르게 찾는데 도움을 줍니다.

이는 데이터베이스에서 쿼리 성능을 향상시키는데 효과적입니다. (특히 읽기 쿼리)

인덱스가 걸려있지 않은 테이블에서 특정 튜플을 찾을때는 full scan을 수행하여 O(N)의 시간이 소요될 수 있지만,

인덱스가 걸려있는 테이블에서 특정 튜플을 찾을때는 B-Tree 기반 인덱스의 경우 O(logN)의 시간이 소요될 수 있습니다.

 

또한 빠르게 정렬(Order by)하거나, 그룹핑(Group by)에도 효과적입니다.

데이터는 데이터베이스에서 어떻게 저장되는가?

데이터는 일반적으로 페이지 또는 블록이라고 하는 고정 크기의 단위로 저장 장치에 저장됩니다. 이 단위의 크기는 저장 시스템과 구성에 따라 몇 킬로바이트에서 몇 메가바이트까지 다양할 수 있습니다(PostgreSQL 기본값은 8k).

DBMS는 이러한 단위로 데이터를 읽고 쓰게 됩니다. 만약 데이터베이스 엔진이 데이터에 대한 추가 메타데이터가 없다면 모든 쿼리에 대해 전체 스캔을 수행해야 할 것입니다. 

Key와 Index의 차이

Key는 데이터베이스 테이블에서 레코드를 고유하게 식별하거나 두 테이블 간의 관계를 설정하는 데 사용되는 컬럼 또는 표현식의 집합입니다. 이러한 키는 기본 키, 후보 키, 외래 키와 같이 여러 종류가 있습니다.

 

인덱스는 데이터베이스에서 데이터의 검색 속도를 향상시키기 위한 자료구조입니다.

인덱스는 특정 컬럼 또는 컬럼의 집합에 대해 생성되며, 이 컬럼들은 '인덱스 키'라고 불립니다.

인덱스는 데이터의 물리적 저장소와는 별개로 관리되며, 사용자는 SQL 문장을 통해 인덱스를 생성, 삭제, 수정할 수 있습니다. 

CREATE INDEX ord_customer_ix ON orders (customer_id);

위 명령문은 orders 테이블의 customer_id 컬럼에 대한 인덱스를 생성하는 SQL 문장입니다. 여기서 customer_id는 '인덱스 키'를 구성하는 컬럼이며, 생성된 인덱스의 이름은 ord_customer_ix입니다.

 

이 인덱스를 통해, 데이터베이스는 customer_id를 기준으로 orders 테이블의 레코드를 더 빠르게 검색할 수 있습니다.

즉, 키와 인덱스 모두 데이터의 효율적인 관리와 검색을 위한 중요한 요소지만, 그 역할과 사용 방식은 서로 다릅니다.

 

참고로 RDBMS는 Primary Key를 생성시 Index를 자동으로 생성해 놓기 때문에, 따로 명시를 하지 않아도 됩니다.

다음은 Index를 확인하는 SQL 명령문입니다.

SHOW INDEX FROM orders;

Composite Index 

• 두 개 이상의 컬럼을 기반으로 생성된 인덱스
• Composite 인덱스는 여러 컬럼의 조합으로 이루어진 키를 사용하여 데이터를 유일하게 식별하므로, 단일 컬럼 인덱스보다 더욱 세밀한 검색과 빠른 검색 성능을 제공
• 예를 들어, `first_name`과 `last_name`이라는 두 개의 컬럼을 가진 테이블에서, 이름과 성을 모두 사용하여 데이터를 검색해야 하는 경우에 Composite 인덱스를 사용하면 더욱 빠르고 효율적인 검색이 가능
• 그러나, Composite 인덱스는 컬럼의 순서에 따라 동작하므로 이 점을 고려하여 인덱스를 생성해야 함
• 인덱스를 구성하는 컬럼들 중에서 가장 빈번하게 검색 조건으로 사용되는 컬럼을 인덱스의 앞쪽에 위치시키는 것이 일반적인 방법
• 또한, Composite 인덱스는 데이터의 삽입, 삭제, 수정 작업이 느려질 수 있으므로, 이러한 연산의 빈도와 데이터 검색의 필요성 사이에서 적절한 균형을 찾아야 합니다.

Composite Index Column 선택

• where절에서 and 조건으로 자주 통합되어 사용되면서 각각의 분포도 보다 두 개 이상의 컬럼이 통합될 때 분포도가 좋아지는 컬럼들 
• 다른 테이블과 조인의 연결고리로 자주 사용되는 컬럼들
• order by에서 자주 사용되는 컬럼들
• 하나 이상의 키 컬럼 조건으로 같은 테이블의 컬럼들이 자주 조회될 때

Covering Index

• 조회하려는 attribute(s)를 index가 모두 가지고 있어서, 추가적인 테이블 접근이 필요없는 인덱스를 말합니다.
• 이 때문에 읽기 성능이 더 빠릅니다.

여러 인덱스 테이블에서 어떤 인덱스를 사용하는지 어떻게 아는가?

주문 번호와 주문 가격 컬럼이 존재한다고 가정해봅시다.

(주문 번호) 인덱스를 하나 만들고, (주문 번호, 주문 가격) 다음 처럼 두 컬럼에 대해 인덱스를 만들 경우,

WHERE 주문 번호 = 1; 과 같은 조건을 걸었을때 (주문 번호), (주문 번호, 주문 가격) 이 두 인덱스 테이블 중 무엇을 참조하게 될까요?

 

이는 Optimizer가 알아서 골라주지만, 원하는 경우 직접 index를 고르는 SQL 명령문을 사용하면 됩니다.

SELECT * FROM orders USE INDEX(주문 번호) WHERE 주문 번호 = 1;

 

Index의 자료구조

B+ Tree 

• B+ Tree (Balanced Tree) 가장 일반적인 인덱스 구조 중 하나
• 읽기 연산은 O(logN)에 시간 복잡도
• 이는 데이터 검색, 삽입, 삭제가 효율적인 자체 균형 트리 구조
• B+ 트리 인덱스에서 각 노드는 여러 키와 자식 노드를 가리키는 포인터를 포함하며, 이는 트리가 균형을 유지하게 함
• 루트 노드는 맨 위에 있고, 맨 아래에 있는 리프 노드는 실제 데이터 포인터를 포함합니다.
• Range 쿼리에 적합

Hash Index

• Hash table을 사용하여 index를 구현
• 읽기 연산은 시간 복잡도 O(1)
• rehashing에 대한 부담이 있음
• '==' 만 가능하며, '>' , '<' 와 같은 범위 비교 연산엔 사용 불가능
• 주로 인 메모리 기반 데이터베이스나 secondary index에서 사용
• multicolumn index의 경우 전체 attributes에 대한 조회만 가능

Bitmap Indexes

• 상대적으로 중복 값이 적은 컬럼에 주로 사용됩니다.
• 이러한 컬럼을 low-cardinality 컬럼이라 합니다. 읽기 위주의 작업과 복잡한 쿼리에 탁월하지만, 쓰기 작업에는 비효율적일 수 있습니다.

Sparse Indexes

• 테이블의 모든 행이 아닌, 일부 행에 대한 정보만 저장합니다.
• 모든 행을 인덱싱할 필요가 없는 특정 사용 사례에서 쿼리 성능을 최적화하도록 설계되었습니다.
• 모든 행에 대한 인덱스 항목을 저장할 필요가 없기 때문에, 전통적인 인덱스에 비해 공간을 절약합니다.

두 개의 인덱스 타입

Clustered Index (Primary key)

• 테이블 내 데이터의 물리적 순서를 결정합니다.
• 하나의 테이블은 오직 하나의 클러스터 인덱스만 가질 수 있습니다.
• 클러스터 인덱스를 테이블에 생성하면, 데이터 행은 인덱싱된 컬럼(들)의 순서에 따라 재배치됩니다.
• 레코드는 Leaf 노드에 저장됩니다.

다음 그림은 id 칼럼에 대한 Clustered B+ 인덱스를 어떻게 구성하는지 보여줍니다.

데이터베이스는 레코드의 id 값을 키로 사용하여 B+ 트리를 구성합니다.

레코드 자체는 B+ 트리의 Leaf 노드에 저장됩니다.

 

그림 1: Clustered Index Diagram

그림 1은 Id에 대한 클러스터드 인덱스 그림 1은 매우 간단한 B+ 트리를 보여주며, 예상대로 leaf 노드는 페이지라는 단위로 저장소에 저장됩니다.

그러나 레코드만 저장되는 것이 아니라 다른 노드들도 저장되며, 실제로는 이 단순화된 다이어그램에서 보이는 것보다 데이터 양이 훨씬 많을 것입니다. 

id가 16인 새 레코드를 추가하면 B+ 트리의 구조가 다음과 같이 변경됩니다

그림 2

 

그림 2: 16을 추가한 후의 Id에 대한 Clustered 인덱스 데이터베이스 엔진은 B+ 트리에 새 레코드를 추가할 때 일련의 작업을 수행합니다. 먼저 관련 인덱스 페이지를 검색하고, 새 레코드를 수용할 수 있도록 B+ 트리를 재구성합니다. 재구성이 완료되면 엔진은 업데이트된 페이지를 저장하고 스토리지에 다시 쓰기 작업을 수행하여 B+ 트리가 최적화된 상태를 유지하도록 합니다.

 

Non Clustered Index (or Secondary Index):

• 테이블 내 데이터의 물리적 순서를 변경하지 않습니다.
• 테이블은 여러 개의 비클러스터 인덱스를 가질 수 있습니다.
• 인덱싱된 컬럼(들)의 복사본과 그 저장 주소로의 포인터를 포함하는 별도의 데이터 구조에 저장됩니다.

그림 3

그림 3은 이메일을 키로 사용하는 B+ 트리를 나타냅니다.

이는 그림 1과 2와 매우 유사하지만 중요한 차이점이 하나 있습니다.

레코드가 leaf 노드에 저장되지 않습니다.

대신, leaf 노드는 레코드의 ID나 저장소에서 레코드의 위치를 포함하고 있습니다.

대부분의 데이터베이스는 값을 ID로 사용하지만, PostgreSQL은 저장소에서 레코드의 위치를 사용합니다.

 

우리가 이메일이 q@e.com이고 ID가 16인 새 레코드를 B+ 트리에 추가하면, 구조는 다음과 같이 변경될 것입니다

그림 4

그림 4: q@email.com을 추가한 후의 이메일에 대한 Non clustered 인덱스 따라서 보셨듯이, 우리가 삽입, 업데이트 또는 삭제를 할 때마다, 데이터베이스 엔진은 B+ 트리에 새 레코드를 추가할 때 일련의 작업을 수행합니다. 엔진은 관련 인덱스 페이지를 검색하는 것으로 시작하여, 새 레코드를 수용할 수 있도록 B+ 트리를 재구성합니다. 재구성이 완료되면, 엔진은 업데이트된 페이지를 저장하고 저장소에 다시 씁니다, 이를 통해 B+ 트리가 최적화된 상태를 유지하게 됩니다.

Index의 장단점

장점

• 인덱스는 단일 행 데이터에 대한 빠른 접근 경로를 제공 (행 속도에만 영향을 미침)
• 인덱싱된 데이터 값을 주어진 경우, 인덱스는 그 값을 포함하는 행의 위치를 직접 가리킴
• 인덱스는 디스크 I/O를 줄이는 여러 방법 중 하나

단점

• 인덱스는 디스크 공간을 차지함
• 인덱싱된 데이터에 DML(데이터 조작)이 발생하면 데이터베이스는 인덱스를 업데이트해야 하는데, 이는 성능 오버헤드를 만듬

인덱스는 어떤 상황에서 사용하는게 유리할까?

• 인덱싱된 열이 자주 쿼리되며, 데이터가 매우 많을 경우
• 조회하려는 데이터가 테이블의 적은 부분을 차지할 경우

ORDER BY/GROUP BY 연산의 동작 과정을 인덱스의 존재여부와 연관지어서 설명해 주세요.

ORDER BY 연산

인덱스가 없는 경우, 데이터베이스는 모든 레코드를 스캔하고, 메모리나 디스크 상의 임시 공간에 복사한 후 정렬 알고리즘을 사용해 결과 집합을 정렬합니다.

이 과정은 I/O 비용과 CPU 리소스를 상당히 소모하므로 비효율적일 수 있습니다.

인덱스가 있는 경우, 데이터베이스는 인덱스를 사용해 레코드를 빠르게 접근하고 이미 정렬된 순서대로 데이터를 가져올 수 있습니다.

따라서 ORDER BY 절이 인덱스와 일치하면, 데이터베이스는 인덱스를 스캔하며 필요한 데이터를 효율적으로 가져올 수 있습니다.

 

GROUP BY 연산

인덱스가 없는 경우, 데이터베이스는 모든 레코드를 스캔하고, 각 그룹에 대한 정보를 유지하며, 필요한 집계 연산을 수행합니다.

이는 ORDER BY와 마찬가지로 상당한 I/O 비용과 CPU 리소스를 소모할 수 있습니다.

인덱스가 있는 경우, 데이터베이스는 인덱스를 통해 레코드를 빠르게 접근하고, 이미 정렬된 데이터를 기반으로 그룹을 빠르게 형성할 수 있습니다.

따라서 GROUP BY 절이 인덱스와 일치하는 경우, 데이터베이스는 인덱스를 스캔하며 효율적으로 그룹화를 수행할 수 있습니다.

참고 자료

https://medium.com/@rimonadel01/introduction-to-database-indexes-9b488e243cc1

Introduction To Database Indexes

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/Database#index

https://docs.oracle.com/en/database/oracle/oracle-database/23/cncpt/indexes-and-index-organized-tables.html#GUID-DE7A95BC-6E4A-47EA-9FC5-B85B54F8CF41

Database Concepts

https://velog.io/@kwontae1313/복합인덱스

복합인덱스(Composite Index)