3주차 - 랜덤I/O, 순차 I/O와 인덱스, B+Tree, B-Tree

질문

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

 

 

랜덤 I/O vs 순차 I/O

 

랜덤 I/O는 디스크에서 비연속적인 위치에 있는 데이터를 읽는 방식이며, 순차 I/O는 데이터를 연속적인 순서로 읽는 방식이다.

 

- 당연하게도 순차 I/O가 더 빠르다. (디스크 상의 연속적인 위치에 저장)

- 데이터베이스 시스템에서는 종종 랜덤 I/O가 필요하다.
데이터베이스에는 다양한 쿼리가 수행되며, 이 쿼리들은 테이블의 여러 위치에 저장된 데이터를 요구하기 때문.
특히 인덱스 검색이나 특정 조건에 맞는 레코드 검색과 같은 작업에서 랜덤 I/O가 필수적이다.

- 인덱스 레인지 스캔은 데이터를 읽기 위해 주로 랜덤 I/O를 사용하며, 풀 테이블 스캔은 순차 I/O를 사용한다.

2. 인덱스에 대해서 설명해주세요.

데이터베이스에서 특정 컬럼의 데이터를 빠르게 검색할 수 있도록 도와주는 자료 구조.

DBMS에서 실제 데이터 레코드를 더 빠르게 찾아가기 위해, 

데이터 레코드를 참조하는 인덱스를 만들고 '정렬' 하여 데이터의 탐색을 더 빠르게 한다. 

- 포인터

인덱스는 특정 컬럼에 대한 포인터를 포함하고 있으며, 이 포인터들은 데이터가 저장된 위치를 가리킨다.

이를 통해 데이터베이스는 전체 테이블을 처음부터 끝까지 살펴보지 않고도(Full Scan) 필요한 데이터를 신속하게 찾을 수 있다.

 

인덱스의 예시 (좌측은 인덱스 포인터 저장 공간)

 

 

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

인덱스의 동작 과정

 

1. 인덱스 생성
   데이터베이스에 인덱스를 생성할 때, 선택된 컬럼의 값과 각 값이 저장된 데이터의 위치를 포인팅하는 구조가 만들어진다. 이 과정에서 인덱스 키는 정렬되어 저장되며, 이는 검색 효율성을 높인다.
   
   
2. 검색 작업
   사용자가 데이터를 검색할 때, 데이터베이스는 먼저 인덱스를 확인한다. 인덱스에 검색하려는 값이 있으면, 인덱스는 해당 값이 저장된 실제 데이터의 위치를 가리킨다. 이를 통해 데이터베이스는 전체 테이블을 스캔하지 않고, 필요한 데이터에 바로 접근할 수 있다.
   
   
3. 데이터 수정
   데이터를 삽입, 삭제, 수정할 때마다 인덱스도 갱신된다. 예를 들어, 새로운 데이터가 삽입되면, 인덱스는 새 데이터의 위치를 가리키는 새로운 엔트리를 추가한다. 삭제의 경우, 해당 데이터를 가리키는 인덱스 엔트리가 제거되며, 데이터 수정의 경우에는 인덱스 엔트리가 갱신된다.
   

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

• tuple이 많이 들어있는 대용량의 relation
• relation에서 대부분의 query가 검색하는 tuple이 2%~4% 인 경우에는 인덱스를 생성하는 것이 좋다.
• 가능하면 한 relation에 세 개 이하의 인덱스를 만드는 것이 좋다.
-> CRUD가 일어나면 인덱스를 많이 업데이트 해야하니까!
• 갱신이 빈번하게 이루어지는 attribute/relation은 인덱스를 많이 만드는 것을 피해야한다.
• file의 record들을 충분히 분할할 수 있어야 한다.
• 가능하면 Integer Attribute에 인덱스를 만드는 것이 가장 좋고, 고정 길이 attribute에 인덱스를 만드는 것이 좋다.
• 대량의 데이터를 삽입할 때는 모든 인덱스를 제거하고 데이터 삽입이 끝난 후에 인덱스들을 다시 생성하는 것이 좋다.
  
  
• https://wkdtjsgur100.github.io/database-index/

데이터베이스 인덱스 기초 개념 정리(인덱스의 정의, 특징, 사용 지침 등)

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

인덱스는 검색 속도를 크게 향상시키지만, 데이터 변경 작업이 많을수록 인덱스의 유지 관리에 드는 비용이 증가한다.

따라서, 자주 검색되고, 조건에 사용되며, 중복도가 낮은 컬럼에 인덱스를 설정해야 한다.

 

인덱스를 생성하면 검색 속도가 향상되지만,

1. 인덱스 자체를 유지 관리하기 위한 추가적인 공간이 필요하고,

2. 데이터 삽입, 삭제, 수정 작업 시 인덱스 역시 갱신(정렬)해야 하므로 이러한 작업의 속도가 느려질 수 있다.

( 인덱스가 많으면 검색 속도는 빨라지지만, 삽입, 삭제, 갱신 작업이 느려진다.)

 

따라서, 인덱스는 검색을 자주 수행하는 컬럼에 대해서만 신중하게 생성해야 한다.

 

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

 

커버링 인덱스(Covering Index)는 특정 질의(query)를 처리하는 데 필요한 모든 데이터를 포함하는 인덱스를 말한다.

 

= 즉, 질의에 의해 요구되는 모든 컬럼들이 인덱스 내에 존재하여,

데이터베이스가 실제 테이블의 데이터를 참조할 필요 없이 인덱스만으로 질의를 완전히 처리할 수 있다는 의미이다.

 

장점

 

- 성능 향상(DB접근 x, 쿼리 간소화 )

커버링 인덱스는 데이터베이스가 실제 테이블에 접근하는 것을 줄여줌으로써, 디스크 I/O를 감소시킨다.

인덱스 자체에서 모든 필요한 데이터를 얻을 수 있기 때문에, 데이터 검색이 더 빨라지며 쿼리 실행 계획이 간소화된다.

 

- 최적화된 인덱스 크기: 필요한 컬럼들만 포함하여 생성하기에, 인덱스의 크기를 최적화할 수 있다.

 

주의점

 

- 인덱스 설계:

커버링 인덱스는 특정 쿼리에 맞춰 설계되에, 어떤 컬럼을 인덱스에 포함시킬지 신중하게 결정해야 한다.

(너무 많은 컬럼을 포함시킬 경우 인덱스의 크기가 커져서 성능이 저하될 수 있다.)

 

7. 다중 컬럼 인덱스(Multi-column index, 복합 인덱스)에 대해서 설명해주세요.

컬럼 하나를 인덱스로 하는 것이 아닌, 두 개 이상(다중)의 컬럼을 결합하여 생성한 인덱스를 말한다.

이런 인덱스는 데이터베이스 내에서 여러 컬럼을 기준으로 데이터를 검색, 정렬, 비교할 때 사용된다.

 

- 만약 A, B 컬럼을 잡는다고 가정하면 A를 기준으로 먼저 정렬하고 이후 B를 다시 재색인하는 식으로 우선 순위가 나누어져 있다..

- MySQL의 경우에는 최대 15개의 다중 컬럼 인덱스를 설정할 수 있다.

- 쿼리의 WHERE 절 조건에 따라 성능이 달라진다. (주로 WHERE 절에 사용된 조건이 다중 컬럼 인덱스를 얼마나 효율적으로 활용할 수 있는지에 따라 쿼리의 실행 속도와 성능이 영향을 받는다.)

 

8. B-Tree 인덱스와 B+Tree 인덱스에 대해 설명해주세요.

B-Tree 구조

인덱스의 가장 일반적인 형태는 B-트리(B-Tree) 구조를 사용한다.

 

 

- B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하며, 그 하위에 자식 노드가 붙어 있는 형태다.

- 가장 하위에 있는 노드를 리프 노드라 한다.

- 루트 노드가 아니고 리프 노드가 아닌 중간의 자식 노드를 브랜치 노드라고 한다.

값을 찾기 위해서 일반적인 트리처럼 좌, 우측만을 사용하지 않고 노드에 저장된 값 사이의 포인터를 통해 탐색한다.

 

< 포인터 탐색 >

위 그래프에서 14라는 값을 찾는다고 하자.

1. 14는 7,15 사이에 있으므로 가운데 연결된 (9, 11) 노드로 내려간다.

2. 14는 11보다 크므로 11의 오른쪽 노드로 내려가서 14라는 값에 도달하게 된다.

 

실제로는 한 노드에 이보다 많은 값들이 정렬된 상태로 존재한다.

 

< 노드 추가/삭제 >

한 노드에 얼마나 많은 값들이 존재할 수 있는지 체크를 하고 값을 맨 아래 리프노드의 적절한 위치에 넣은 후 제 자리를 찾아가게 된다. 이를 페이징이라고 한다.

 

예를 들어, 13이라는 값이 추가 되면 최초에는 (12,14) 노드 사이에 들어간다.

하지만 한 노드에 2개 값만 존재할 수 있으므로(위 트리의 경우에만) 13이 한 단계 한 단계 레벨을 올리며 자기 자신의 자리를 찾아가게 된다.

 

B+Tree 구조

데이터의 검색에는 B-Tree가 유리하지만, 모든 데이터를 풀 스캔하려면 결국 모든 트리를 전부 방문해야 한다.

이러한 단점을 개선한 것이 B+Tree이다.

 

B-Tree는 모든 노드에 키와 데이터를 저장하지만, B+Tree는 리프 노드에만 데이터를 저장하고 리프 노드가 연결리스트로 연결되어 있다.

 

 

 

장점

- 리프노드를 제외한 루트, 브랜치 노드에는 데이터를 저장하지 않기 때문에 메모리가 남고 그 남는 메모리를 중간 브랜치 노드에 키 값을 저장하는데 사용할 수 있다. (즉 트리의 높이가 낮아지므로 검색 속도가 빨라진다. )

 

- 풀 스캔을 하는 경우에는 데이터가 존재하는 리프 노드를 스캔하면 된다.

모두 Linked List로 연결되어 있으므로  유리하다.

범위 스캔의 경우에도 LinkedList를 통해 효율적으로 순차 검색을 할 수 있다. (랜덤 검색보다 빠르다!)

 

단점

- 모든 데이터가 리프노드에 있기 때문에 값을 찾기 위해서 어떻게든 리프노드에 도달해야만 한다.

- 브랜치 노드에서 키를 올바르게 찾아가기 위해 중복된 키가 존재할 수도 있다.

 

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

키의 해시 값을 사용하여 인덱스를 구성하는 방식. 등호(=) 연산에 유용하다.

 

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

데이터를 인덱스의 순서대로 물리적으로 저장하는 인덱스.

 

- Clustered Index는 개발자가 설정하는 Index가 아닌 MySQL이 자동으로 설정하는 Index이다.

해당 인덱스의 우선순위는 다음과 같다.

1. 테이블에 Auto increments 값으로 PK가 있다면 해당 컬럼이 Clustered Index가 된다.
2. 1이 없다면 컬럼 중 Unique컬럼을 Clustered Index로 선정한다.
3. 1, 2도 없을 경우 MySQL에서 내부적으로 Hidden Clustered Index Key (row ID)를 만들어 Clustered Index로 사용한다.

도식으로 알아보는 클러스터 구조 비교

 

 

- 한개의 테이블에 한개씩만 만들 수 있다 (ex : Primary Key)
- 본래 인덱스는 생성 시 데이터들의 배열정보를 따로 저장하는 공간을 사용하나, 클러스터 인덱스는 따로 저장하는 정보 공간을 적게 사용하면서 테이블 공간 자체를 활용한다.

 

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

인덱스를 사용하여 데이터를 찾는 방식이다. (Full scan보다 효율적일 수 있다.)

 

Index Range Scan

B-tree 인덱스의 가장 일반적이고 정상적인 형태의 액세스 방식.

인덱스 루트에서 리프 블록까지 수직적 탐색을 하고, 필요한 범위만큼 수평적 탐색하는 스캔 방식이다.

 

Index Full Scan

Index Full Scan은 수직적 탐색 없이 인덱스 리프 블록 처음부터 끝까지 수평적으로 탐색하는 방식이다.

데이터 검색을 위한 최적의 인덱스가 없을 때 차선으로 선택된다.

 

이 외에도 인덱스 스캔 역시 순차, 랜덤 스캔이 가능하다.

 

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

 

데이터베이스가 쿼리를 어떻게 실행할지 결정하는 방식.

= 사용자가 SQL을 실행하여 데이터를 추출하려고 할 때, 옵티마이저가 수립하는 작업 절차이다.

즉, 'SQL을 데이터베이스에서 어떻게 처리하여 데이터를 가져올것인가?’를 예상하는 계획표

 

데이터베이스에서 전달된 SQL문은 파싱 > 최적화 > 실행 과정을 거쳐서 처리된다.

 

https://coding-factory.tistory.com/743

 

실행 계획을 분석하여 쿼리 최적화를 수행할 수 있다.

 

13 힌트에 대해서 설명해주세요.

 

데이터베이스 쿼리 최적화에 사용되는 지시어.

쿼리 실행 계획을 개발자가 직접 제어할 수 있도록 도와준다.

 

예를 들어, 특정 인덱스를 사용하도록 강제하거나 특정 조인 방식을 선택하는 데 사용될 수 있다.

 

이런 식으로 옵티마이저가 실행 계획을 짤 때, 지시를 내릴 수 있다.

 

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

 

실행 계획을 확인하거나, 쿼리 실행 시간과 리소스 사용량을 분석하여 인덱스의 성능을 평가한다.

 

15. 인덱스 사용시 주의해야할 점에 대해서 알려주세요.

인덱스 오버헤드, 쓰기 성능 저하, 적절하지 않은 인덱스 사용으로 인한 성능 저하 등을 주의해야 한다.

 

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

GROUP BY 절에 사용되는 컬럼에 인덱스가 있으면 집계 성능을 향상시킬 수 있다.

17. 이름, 국가, 성별이 있는 테이블에서 인덱스를 어떻게 걸어야할까요?

이름, 국가, 성별 컬럼에 따라 다르지만, 일반적으로 자주 검색되거나 조건에 사용되는 컬럼에 인덱스를 설정한다.

예를 들어, 국가별 검색이 자주 이루어진다면 '국가' 컬럼에 인덱스를 설정할 수 있다.

 

 

 

 

참조

 

1.

 

https://hyuuny.tistory.com/205

[MySQL] 인덱스 1

 

 

https://velog.io/@bsjp400/Database-DB-%EC%9D%B8%EB%8D%B1%EC%8B%B1Indexing%EC%9D%B4%EB%9E%80

[Database] DB 인덱싱(Indexing)이란?

 

https://rachel0115.tistory.com/entry/MySQL-%EC%9D%B8%EB%8D%B1%EC%8A%A4-INDEX-%EC%A0%95%EB%A6%AC-%EB%8F%99%EC%9E%91-%EB%B0%A9%EC%8B%9D-%EC%83%9D%EC%84%B1-%EC%82%AD%EC%A0%9C-%EC%84%A4%EA%B3%84

[MySQL] - 인덱스 (INDEX) 정리 (동작 방식, 생성, 삭제, 설계)

 

https://wkdtjsgur100.github.io/database-index/

데이터베이스 인덱스 기초 개념 정리(인덱스의 정의, 특징, 사용 지침 등)

 

https://kyungyeon.dev/posts/66/

DB Index 동작원리를 알아보자

 

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

[자료구조] 그림으로 알아보는 B+Tree

 

https://medium.com/peppermint100/db-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-f940902f61a2

DB 인덱스 자료구조

 

https://devuna.tistory.com/35

[SQL 튜닝] 오라클 힌트(hint)의 개념/ 사용법/자주쓰이는힌트 정리