Week3 Index

인덱스

랜덤 I/O와 순차 I/O에 대해 설명해주세요

랜덤 I/O: 헤드가 디스크의 여러 위치로 빠르게 이동해야 하기 때문에 탐색 시간이 길어지고, 그 결과 성능이 저하됩니다. 비연속적인 위치에서 데이터를 읽거나 쓰는 방식입니다. 파일 시스템이나 데이터베이스에서 데이터가 디스크의 여러 위치에 흩어져 있을 때 주로 발생합니다.

• 특징: 데이터를 읽고 쓰는 위치가 임의적이므로, 디스크의 헤드가 자주 움직여야 합니다. 특히 하드 디스크(HDD)에서 이 방식은 성능 저하를 초래할 수 있습니다. 디스크 헤드의 이동(시크 타임)이 많이 발생하고, 디스크 회전 대기 시간이 길어질 수 있기 때문입니다.

• 장점: 특정 위치에 빠르게 접근하여 데이터를 처리할 수 있으므로, 소량의 데이터를 여러 곳에서 읽어야 하는 경우에 유리합니다.

• 단점: 물리적 디스크의 특성상, I/O 성능이 낮아질 수 있습니다. 특히 하드 디스크(HDD)에서는 랜덤 접근이 비효율적입니다.

예시

• 데이터베이스에서 인덱스를 통해 특정 레코드에 접근할 때

• 파일 시스템에서 여러 파일을 동시에 읽거나 쓸 때

순차 I/O: 헤드가 디스크에서 연속적으로 데이터를 읽기 때문에 탐색 시간이 줄어들어 성능이 훨씬 빠릅니다.

순차 I/O는 연속적인 데이터 블록을 순서대로 읽거나 쓰는 방식입니다. 이는 디스크에 저장된 데이터가 연속적인 위치에 저장되어 있을 때 주로 발생합니다.

• 특징: 데이터를 순차적으로 처리하므로, 디스크 헤드가 한 번에 긴 데이터 블록을 읽거나 쓸 수 있어 I/O 효율성이 높습니다. 특히 하드 디스크에서는 순차 I/O가 매우 빠르며, 디스크 회전과 헤드 이동이 최소화됩니다.

• 장점: 대용량 데이터를 빠르게 처리할 수 있으며, 성능이 매우 우수합니다. 일반적인 HDD나 SSD 모두 순차 I/O에서 높은 성능을 보입니다.

• 단점: 특정 위치에 있는 데이터를 즉시 접근하기보다는, 전체 데이터 흐름을 따라 읽거나 써야 하기 때문에 유연성이 떨어질 수 있습니다.

예시

• 로그 파일에 데이터를 추가할 때 (로그는 주로 순차적으로 쓰여짐)

• 대용량 파일을 연속적으로 읽을 때 (예: 비디오 파일)

인덱스가 뭔가요?

• 인덱스는 데이터베이스에서 검색 성능을 높이기 위해 사용하는 자료 구조

• 인덱스가 없으면, 테이블의 모든 데이터를 처음부터 끝까지 스캔하는 풀 스캔이 발생하지만, 인덱스를 사용하면 인덱스를 통해 필요한 레코드의 위치를 빠르게 조회

• 인덱스는 주로 B-트리(B-tree) 구조로 구현되며, 이는 균형 잡힌 트리로서 삽입, 삭제, 검색 시 일정한 성능을 보장

• 하지만 인덱스는 삽입, 수정, 삭제 작업 시 추가적인 오버헤드를 발생시킵니다. 인덱스는 항상 정렬된 상태를 유지해야 하므로, 레코드를 수정하거나 삭제할 때 인덱스도 함께 갱신

인덱스의 동작 방식에 대해서 설명해주세요

인덱스 테이블에 특정 컬럼들만 저장하고 해시 또는 B트리를 통해 빠르게 검색이 가능합니다.

B-트리

• B-트리 구조로 구현. 균형 이진 트리와 유사하지만, 각 노드가 여러 개의 자식 노드를 가질 수 있는 구조

• 데이터 삽입, 삭제, 검색 작업이 log(n)의 시간 복잡도

• 내부 노드에는 해당 노드의 키 값과 함께 각 자식 노드로 이동하기 위한 포인터가 포함되어 있으며, 검색 대상이 내부 노드의 키 값에 맞는 경우에는 리프 노드까지 가지 않고도 데이터를 얻을 수 있습니다.

해시

해시 인덱스는 특정 값에 대해 해시 함수를 적용하여 데이터가 저장된 위치를 빠르게 찾는 방식입니다. 이 방식은 정확한 값을 검색할 때 매우 효율적이지만, 범위 검색에는 적합하지 않습니다.

• 해시 값 계산: 해시 함수는 입력된 키 값을 기반으로 고유한 해시 값을 계산합니다.

• 해시 버킷: 계산된 해시 값은 특정 버킷(bucket)에 매핑됩니다. 해당 버킷에 저장된 데이터를 읽어와 비교하여 원하는 데이터를 찾습니다.

어떤 기준으로 인덱스를 설정해야 할까요?

• 유일성, 카디널리티, 검색 패턴, 데이터 수정 빈도 등을 종합적으로 고려

• 카디널리티가 높은 컬럼: 인덱스는 주로 카디널리티가 높은 컬럼에 설정하는 것이 좋습니다. 카디널리티란 해당 컬럼에서 유일한 값의 개수를 의미

• 자주 검색되는 컬럼: 인덱스는 검색 조건에 자주 사용되는 컬럼에 설정하는 것이 효율적입니다. WHERE 절에서 자주 사용되는 컬럼이나 JOIN에서 자주 쓰이는 컬럼에 인덱스를 걸면, 검색 속도를 크게 향상시킬 수 있습니다.

• 삽입/수정/삭제 빈도 고려.

테이블에 인덱스를 많이 설정하면 좋을까요?

• 너무 많은 인덱스를 설정하는 것은 성능에 부정적인 영향

• 쓰기 작업의 성능 저하 (읽기 성능과 쓰기 성능 간의 트레이드 오프)

• 인덱스 저장 공간

• 쿼리 옵티마이저의 인덱스 선택 문제: 옵티마이저가 잘못된 인덱스를 선택할 가능성

커버링 인덱스(Covering Index)에 대해서 설명해주세요

• 쿼리에서 필요한 모든 데이터를 인덱스 자체에서 조회할 수 있는 인덱스. 즉, 인덱스만으로 결과를 반환할 수 있는 경우.

• 디스크 I/O 감소: 테이블의 데이터를 직접 읽는 대신, 인덱스만으로 데이터를 가져올 수 있으므로 디스크 I/O가 줄어들어 성능이 크게 향상

• 성능 최적화

CREATE INDEX idx_department_name ON employees (department, id, name);
이 인덱스는 department, id, name 열을 포함합니다. 이제 동일한 쿼리를 실행하면:

SELECT id, name FROM employees WHERE department = 'Sales';

이 경우, 인덱스 idx_department_name이 department, id, name 열을 모두 포함하고 있기 때문에, 데이터베이스는 인덱스만으로도 필요한 모든 데이터를 가져올 수 있습니다. 즉, 테이블에 접근할 필요 없이 인덱스만으로 쿼리가 처리됩니다.

다중 컬럼 인덱스(복합 인덱스)에 대해서 설명해주세요

• 두 개 이상의 컬럼을 하나의 인덱스로 묶어 한 번에 여러 조건을 기반으로 검색 성능을 최적화할 수 있는 인덱스

• 컬럼의 순서에 따라 성능이 달라집니다. (예를 들어, (A, B, C)로 설정된 인덱스는 **첫 번째 컬럼(A)**에 기반한 검색에서만 성능 향상이 있습니다. 만약 WHERE B = ?와 같이 두 번째 컬럼만 검색할 경우에는 인덱스가 제대로 사용되지 않을 수 있습니다.) 선두 컬럼부터 차례대로 조건에 맞는 값을 찾아나가며, 따라서 쿼리의 조건이 선두 컬럼과 일치할 때에만 인덱스가 효과적으로 사용

• 향상된 검색 성능

• 특정 쿼리에 최적화: WHERE A = ? AND B = ?

• 메모리 사용 증가

• 삽입/삭제/수정 시 성능 저하

• 쿼리 옵티마이저 선택 문제

B-, B+ 트리 인덱스에 대해 설명해주세요.

자가 균형 트리(Self-balancing Tree)로, 데이터베이스 인덱스에서 효율적인 검색, 삽입, 삭제를 위해 사용되는 트리 구조

B- 트리

• B-Tree는 내부 노드와 리프 노드 모두에 데이터와 키 값을 저장

• 내부 노드에서 원하는 데이터를 찾으면 리프 노드까지 탐색할 필요가 없음

• 범위 검색에는 비효율적

B+ 트리

• 모든 데이터를 리프 노드에만 저장하는 구조

• 범위 검색에 유리 (순차 검색이 빠름)

• 메모리 효율성: 내부 노드에 데이터를 저장하지 않기떄문에 더 많은 키를 저장할 수 있어서 트리의 깊이가 작음

Hash 인덱스에 대해 설명해주세요

• 정확한 값 일치 검색에 매우 빠른 성능 하지만 범위 범색 불가능

• 데이터를 정렬하지 않기 때문에, BETWEEN, >, < 같은 조건을 사용할 때 매우 비효율적

• 체이닝 필요: 해시 함수는 서로 다른 입력 값이 동일한 해시 값을 가질 수 있는 충돌(Collision)이 발생할 수 있습니다.

해시 충돌의 발생 원리

해시 함수는 입력 값을 일정한 범위 내의 값으로 변환하는 함수입니다. 해시 테이블의 크기는 유한하므로 해시 함수가 생성할 수 있는 해시 값의 수 역시 유한합니다. 반면, 입력 값은 매우 다양하고 무한한 경우가 있을 수 있기 때문에 서로 다른 두 입력 값이 같은 해시 값을 가질 수밖에 없습니다. 이때 해시 테이블에서 동일한 해시 값에 여러 입력 값이 할당되면서 충돌이 발생합니다.

• 해시 충돌 해결 방법

  • 체이닝: 동일한 해시 값을 가진 데이터를 연결 리스트로 관리하는 방식입니다.

  • 오픈 어드레싱: 충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장하는 방식입니다.

연결 리스트로 연결된 데이터 조회 과정

1. 해시 함수 적용: 조회하려는 키에 해시 함수를 적용하여 해당 키가 저장된 버킷을 결정합니다. 해시 함수는 주어진 키에 대해 일정한 해시 값을 계산하고, 그 해시 값에 해당하는 버킷을 반환합니다.

   예를 들어, 해시 함수가 다음과 같이 정의되어 있다고 가정합니다:

   plaintext코드 복사해시 값 = key % 10

   키 key = 12에 대해 해시 함수는 다음과 같은 해시 값을 반환합니다.

   plaintext코드 복사12 % 10 = 2

   따라서 키 12는 버킷 2에 저장되어 있음을 알 수 있습니다.

2. 해당 버킷의 연결 리스트 탐색: 해시 테이블에서 버킷 2로 이동하여 그 버킷에 저장된 연결 리스트를 조회합니다. 연결 리스트는 충돌로 인해 같은 해시 값을 가지는 여러 항목이 저장되어 있으므로, 이 리스트에서 원하는 키를 찾아야 합니다.

3. 연결 리스트에서 키 비교: 연결 리스트의 각 노드를 순차적으로 탐색하며, 저장된 키와 조회하려는 키를 하나씩 비교합니다. 만약 같은 키를 찾으면 해당 키에 연결된 데이터를 반환합니다.

4. 키가 일치하는 데이터 반환: 연결 리스트에서 조회하려는 키를 찾았다면, 해당 키에 저장된 데이터 값을 반환합니다.

5. 키가 일치하지 않으면 조회 실패: 연결 리스트를 모두 탐색했지만 일치하는 키를 찾지 못하면, 해당 키에 대한 데이터는 해시 테이블에 존재하지 않음을 의미합니다.

클러스터링 인덱스에 대해서 설명해주세요

• 데이터베이스 테이블의 물리적인 저장 순서를 인덱스의 순서와 일치시키는 방식(해당 인덱스의 값에 따라 데이터가 디스크에 물리적으로 정렬되어 저장)

• 테이블당 단 하나만 존재 가능. 기본키 / 고유키에 따라 정렬됨

• InnoDB와 같은 스토리지 엔진에서는 자동으로 기본키가 클러스터링 인덱스가 됨

• 빠른 범위 검색

• 인접 데이터 액세스

• 데이터 수정 시 오버헤드(재배치)

인덱스 스캔 방식에 대해 설명해주세요.

인덱스 유니크 스캔

• 인덱스 유니크 스캔은 고유한 값을 검색할 때 사용됩니다. 이 방식은 주로 프라이머리 키(Primary Key)나 유니크 인덱스(Unique Index)에 대해 정확한 값 일치 검색을 수행하는 경우 사용됩니다. 인덱스에서 해당 키를 바로 찾아가기 때문에 성능이 매우 빠릅니다.

인덱스 레인지 스캔

• 검색할 데이터의 범위가 정해졌을 때 사용되는 스캔 방식 (WHERE, BETWEEN, <, > 등)

인덱스 시크

• B-트리(B-Tree) 또는 B+트리(B+Tree) 구조를 사용하여 빠르게 특정 값 또는 좁은 범위의 값을 찾는 방식입니다.

• 트리 구조를 활용하여 루트 노드부터 리프 노드까지 검색하면서 조건에 맞는 데이터를 효율적으로 찾습니다.

인덱스 풀 스캔

• 인덱스의 처음부터 끝까지 모든 엔트리를 순차적으로 스캔하는 방식입니다.

• 테이블 전체를 읽는 것이 아닌, 인덱스에 저장된 특정 열만 읽기 때문에 테이블 풀 스캔(Table Full Scan)보다 효율적일 수 있습니다. (왜냐하면 인덱스는 테이블의 전체 컬럼을 읽지 않고, 필요한 컬럼만 포함하고 있기 때문입니다.)

• 모든 레코드를 인덱스를 통해 검색하지만, 트리 구조의 장점(빠른 탐색)을 활용하지 않고 순차적 탐색이 발생합니다.

  예시:

  SELECT * FROM employees WHERE department_id IS NOT NULL;

  만약 department_id에 인덱스가 있다면, 쿼리의 결과가 많은 데이터를 반환할 경우 인덱스 풀 스캔이 발생할 수 있습니다. 이때 테이블의 모든 열을 읽지 않고, 인덱스에 포함된 department_id와 관련된 데이터만을 순차적으로 스캔합니다.

인덱스 패스트 풀 스캔 (Index Fast Full Scan)

• 인덱스를 정렬되지 않은 순서로 병렬로 읽는 방식입니다.

• 일반적인 인덱스 풀 스캔보다 더 빠르게 인덱스를 조회할 수 있지만, 인덱스의 정렬이 유지되지 않으므로 범위 검색에 적합하지 않습니다.

• 빠르게 데이터를 읽어와야 하지만 순서가 중요하지 않을 때 사용됩니다.

Table Full Scan vs Index Full Scan

테이블 풀 스캔은 모든 컬럼에 대해서 읽은 후에 조건을 확인합니다.

인덱스 풀 스캔은 일부 컬럼만 저장되어서 디스크에서 읽어야 하는 데이터 양이 적습니다.

레코드 수는 같아도, 읽어야 하는 총 데이터 양에서 차이가 납니다.

쿼리 실행 계획에 대해서 설명해주세요. 실행 계획을 확인해본 적이 있나요?

• 데이터베이스가 SQL 쿼리를 어떻게 실행할지에 대한 상세한 계획

• 옵티마이저의 실행 계획은 그 과정에서 테이블에 어떻게 접근할 것인지, 어떤 인덱스를 사용할 것인지, 조인을 어떻게 처리할 것인지 등을 보여줍니다.

• EXPLAIN 키워드를 사용. EXPLAIN SELECT * FROM users WHERE age = 30;

쿼리힌트가 뭔가요?

• 옵티마이저에게 특정 실행 계획을 따르도록 지시하는 것.

• MySQL에서는 USE INDEX 같은 힌트를 사용할 수 있습니다. SELECT * FROM users USE INDEX (idx_age) WHERE age = 30;

인덱스가 잘 동작하고 있는지 어떻게 확인할 수 있을까요?

• 쿼리 실행 계획(EXPLAIN)을 확인

• 쿼리 성능 테스트

• 시스템 테이블로 불필요한 인덱스 식별

인덱스 사용시 주의할점

• 인덱스의 개수

• 중복인덱스: 동일한 컬럼에 여러개의 인덱스

• 카디널리티 고려 (유일한 값의 개수)

• 충분히 데이터양이 큰지 확인

GROUP BY 사용 시 인덱스가 걸리는 조건에 대해 설명해주세요

• 인덱스 컬럼의 순서: GROUP BY 절에서 사용하는 컬럼이 인덱스에 설정된 순서와 일치해야 인덱스를 사용 가능 (GROUP BY a,b,c - OK / GROUP BY b,c - X)

• GROUP BY 구문에서 사용된 컬럼이 모두 인덱스에 포함되어야 합니다.

GROUP BY는 결과를 정렬하는데 인덱스는 이미 정렬되어 있기떄문에 그루핑이 가능해집니다.

예시로 이해하기

1. 올바른 순서로 GROUP BY 하는 경우

인덱스가 (a, b, c) 순서로 설정된 경우를 가정해봅시다.

CREATE INDEX idx_abc ON table_name(a, b, c);

SELECT a, b, c, COUNT(*)
FROM table_name
GROUP BY a, b, c;

이 경우:

• a를 기준으로 먼저 데이터를 정렬하고, b를 기준으로 그 안에서 다시 데이터를 정렬하며, 마지막으로 c를 기준으로 정렬된 데이터가 인덱스에 저장됩니다.

• GROUP BY a, b, c는 인덱스의 정렬 순서를 그대로 따르므로, 인덱스를 그대로 사용하여 데이터를 효율적으로 그룹핑할 수 있습니다. 인덱스를 타고 내려가면서 정렬된 데이터를 빠르게 탐색할 수 있습니다.

2. 중간 컬럼을 건너뛰고 GROUP BY 하는 경우

SELECT b, c, COUNT(*)
FROM table_name
GROUP BY b, c;

이 경우:

• 인덱스는 a를 기준으로 먼저 정렬되었기 때문에, a를 건너뛰고 b, c만으로 그룹핑하려는 경우 인덱스를 활용할 수 없습니다.

• 이는 인덱스가 a로 먼저 정렬된 상태에서 b와 c로 그룹핑을 진행할 수 없기 때문입니다. 인덱스는 a의 값에 따라 첫 번째로 분류된 데이터 하위에서 b, c가 정렬된 상태이므로, a를 무시하고 b, c만을 기준으로 그룹핑하는 것이 불가능합니다.

3. 부분적으로 GROUP BY 하는 경우

SELECT a, b, COUNT(*)
FROM table_name
GROUP BY a, b;

이 경우:

• 인덱스가 (a, b, c) 순서로 설정되어 있고, GROUP BY에서 a와 b만 사용하면 인덱스는 사용될 수 있습니다.

• 인덱스는 a와 b까지는 정렬된 상태로 저장되어 있기 때문에, GROUP BY a, b는 인덱스를 활용하여 효율적으로 그룹핑할 수 있습니다. c는 무시되더라도 문제가 되지 않습니다.

왜 GROUP BY b, c는 인덱스를 사용하지 못하는가?

• 인덱스가 a부터 정렬된 상태이기 때문에, 인덱스는 a의 정렬 없이 b, c로 바로 접근할 수 없습니다.

• B-트리 구조는 첫 번째 컬럼을 기준으로 데이터를 분류하고, 그 하위에서 두 번째, 세 번째 컬럼이 정렬되기 때문에, 첫 번째 컬럼을 건너뛰고 그다음 컬럼들만 사용한 GROUP BY는 인덱스가 트리의 정렬된 특성을 제대로 활용할 수 없게 만듭니다.

정리

• 인덱스의 컬럼 순서와 GROUP BY 절의 컬럼 순서는 일치해야 합니다.

• 첫 번째 컬럼을 기준으로 데이터가 정렬되기 때문에, GROUP BY에서 첫 번째 컬럼을 건너뛰면 인덱스가 제대로 사용되지 않습니다.

• 부분적으로 GROUP BY에서 인덱스의 첫 번째부터 연속된 컬럼만 사용하면, 인덱스는 효과적으로 사용될 수 있습니다.