💻 코딩 일기 : [SQL] '인덱스(INDEX): B-Tree' 편

🔔 '인덱스'에 대해서 알아보자!

💟 인덱스 개념

데이터베이스 인덱스는 데이터베이스에서 데이터를 더 빠르게 검색(튜플 빠르게 조회)할 수 있도록 돕는 자료구조입니다.

인덱스가 없는 경우: Full Scan

• Full Scan:
  • 정의: 인덱스가 없는 경우, 데이터베이스는 원하는 데이터를 찾기 위해 테이블의 모든 행을 하나씩 검사해야 합니다.
  • 시간 복잡도: O(N). 여기서 N은 테이블의 전체 행 수입니다.
  • 성능: 큰 테이블의 경우, Full Scan은 매우 느립니다. 특히 수백만 개의 행을 가진 대형 테이블에서는 심각한 성능 문제를 초래할 수 있습니다.

인덱스가 있는 경우

• 빠른 검색:
  • 인덱스를 사용한 검색: 인덱스가 있는 경우, 데이터베이스는 특정 값을 찾기 위해 인덱스를 사용하여 검색 범위를 좁힐 수 있습니다.
  • 시간 복잡도: 일반적으로 B-Tree 인덱스를 사용하면 O(log N)의 시간 복잡도를 가집니다.
• 빠른 정렬 및 그룹화:
  • 정렬(ORDER BY): 인덱스가 있는 경우, 이미 정렬된 순서대로 저장된 데이터를 빠르게 가져올 수 있습니다. 예를 들어, 특정 컬럼에 대해 클러스터형 인덱스가 걸려 있다면, 해당 컬럼으로 ORDER BY를 수행할 때 빠르게 정렬된 결과를 얻을 수 있습니다.
  • 그룹화(GROUP BY): 인덱스를 사용하면 그룹화 작업도 더 빠르게 수행될 수 있습니다. 특히 그룹화 대상 컬럼에 인덱스가 있다면, 데이터베이스가 인덱스를 사용해 그룹을 빠르게 식별하고 집계할 수 있습니다.

💟 인덱스 생성

이미 테이블이 생성된 후 인덱스 지정

1. 인덱스 생성:

   • SQL 문: CREATE INDEX 인덱스명 ON 테이블명 (컬럼명);
   • 예제: CREATE INDEX student_name_idx ON student (name);
   • 이 명령어는 student 테이블의 name 컬럼에 대해 인덱스를 생성합니다. 이 인덱스는 중복된 값이 있을 수 있습니다.

2. 고유 인덱스 생성:

   • SQL 문: CREATE UNIQUE INDEX 인덱스명 ON 테이블명 (컬럼명1, ...);
   • 예제: CREATE UNIQUE INDEX classroom_id_number_idx ON student (classroom_id, number);
   • 이 명령어는 classroom_id와 number 속성을 조합하여 고유 인덱스를 생성합니다. 같은 반(classroom_id) 내에서는 번호(number)가 중복되지 않도록 보장합니다.

테이블 생성 시 인덱스 지정

처음 테이블을 생성할 때 인덱스를 지정할 수도 있습니다.

CREATE TABLE student (
    id INT PRIMARY KEY,
    name VARCHAR(20) NOT NULL,
    classroom_id INT NOT NULL,
    number INT NOT NULL,
    INDEX student_name_idx (name),
    UNIQUE INDEX classroom_id_number_idx (classroom_id, number)
);

• PRIMARY KEY: id 필드는 기본 키로 지정되어 있으며, 기본 키에는 자동으로 인덱스가 생성됩니다.
• INDEX: name 필드에 대해 일반 인덱스를 생성합니다.
• UNIQUE INDEX: classroom_id와 number 필드를 조합하여 고유 인덱스를 생성합니다. 이를 통해 같은 반에서 번호가 중복되지 않도록 합니다.
• 인덱스명 생략 가능: 인덱스를 생성할 때 이름을 생략할 수 있습니다. 이 경우 데이터베이스 시스템이 자동으로 이름을 생성합니다.

복합 인덱스 (Composite Index)

• 복합 인덱스: 두 개 이상의 열을 조합하여 생성한 인덱스를 말합니다.
  • 예제: UNIQUE INDEX classroom_id_number_idx (classroom_id, number)
  • 이런 복합 인덱스는 classroom_id와 number의 조합이 고유하도록 보장합니다.
  • 복합 인덱스는 여러 열을 기준으로 검색 조건이 있을 때 유용합니다.

인덱스 조회

SHOW INDEX FROM student;

student 테이블에 생성된 모든 인덱스를 보여줍니다. 인덱스의 이름, 열, 고유 여부 등을 확인할 수 있습니다.

💟 B-Tree(Balanced Tree, 균형 트리) 구조

• 각 노드는 여러 개의 키 값과 자식 포인터를 가지고, 트리의 높이가 최소화되어 모든 연산이 O(log N) 시간 복잡도로 수행됩니다.
• 이진 탐색(Binary Search)을 사용할 수 있기 때문에 데이터를 빠르게 찾을 수 있습니다.

이진 탐색 트리 :
1. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖는다.
2. 오른쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 큰 값을 갖는다.
3. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리이다.

🎈 B-Tree 예제

1. Where a = 9

• Members 테이블이 있고, a 필드에 대한 인덱스가 있다고 가정합니다.
• 인덱스는 a 값과 Members 테이블의 튜플을 가리키는 포인터로 구성됩니다.

• 인덱스에서 a = 9를 찾기 위해 binary search를 수행합니다.
• 가운데 값을 선택하여 비교합니다.

Step 1:

• 인덱스 중간 값: 7 (a=7)
  • 7 < 9이므로 아래쪽 부분을 무시하고 위쪽 부분을 탐색

Step 2:

• 남은 인덱스 값: [7, 9, 10]
• 인덱스 중간 값: 7 (a=7)
  • 7 < 9이므로 아래쪽 부분을 무시하고 위쪽 부분을 탐색

Step 3:

• 남은 인덱스 값: [9, 10]
• 인덱스 중간 값: 9 (a=9)
  • 9 == 9이므로 값을 찾았습니다.
  • 이 값을 가리키는 포인터를 따라가서 Members 테이블에서 해당 튜플을 선택합니다.

2. INDEX(a), Where a = 7 And b = 95

• 인덱스에서 a = 7을 찾기 위해 binary search를 수행합니다.

Step 1:

• 인덱스 중간 값: 7 (a=7)
  • 7 < 9이므로 아래쪽 부분을 무시하고 위쪽 부분을 탐색

Step 2:

• 남은 인덱스 값: [7, 9, 10]
• 인덱스 중간 값: 7 (a=7)
  • 7 < 9이므로 아래쪽 부분을 무시하고 위쪽 부분을 탐색
  • 7 == 7에 해당하는 Members의 b가 95인 튜플 탐색

단점 : a에 대한 인덱스를 사용하여 a = 7을 찾고, 그 다음 b = 95를 확인하기 위해 Members 테이블에서 전체 탐색(full scan)을 수행해야 합니다.

3. INDEX(a,b), Where a = 7 And b = 95

• 인덱스에서 a = 7, b = 95을 찾기 위해 binary search를 수행합니다.
• a를 기준으로 먼저 정렬하고 a의 값이 같으면 b를 기준으로 정렬됩니다.

Step 1:

• 인덱스 중간 값: 7 (a=7)
  • 7 < 9이므로 아래쪽 부분을 무시하고 위쪽 부분을 탐색

Step 2:

• 남은 인덱스 값: [7, 9, 10]
• 인덱스 중간 값: 7 (a=7)
  • 7 < 9이므로 아래쪽 부분을 무시하고 위쪽 부분을 탐색
  • a가 7 == 7이면 b를 비교
  • b가 95를 기준으로 아래 쪽에 있는 b = 55와 b = 95를 비교하는데 95가 더 크기 때문에 아래 쪽으로 갈 수록 95보다 작으니 이 부분도 제외합니다.
  • 위쪽에 있는 b = 98은 95보다 크니 제외합니다.
  • 따라서 a = 7 , b = 95인 튜플은 하나가 있습니다.