Tech Log 🛠️

0. 만약 인덱스가 없었다면

인덱스 없이 테이블에 대한 탐색을 한다고 가정해보자

num의 값이 27인 행을 찾는 다고 가정했을 때 인덱스가 없다면 , 정렬 되지 않은 데이터를 처음부터 찾아야한다.

이럴 경우 하나의 데이터를 찾기 위해서 최악의 경우 모든 값을 탐색하는 풀 스캔을 해야할 수도있다.

이는 매우 비효율적인 방법이다.

인덱스가 없는 경우 어떤 현상이 일어나는 지 알아보았으니, 그럼 이제 인덱스가 적용 된 경우를 살펴보자

처음 예시와의 차이점은 데이터가 정렬되어 있고 무작정 처음부터 조회하지 않는다.

이 경우 정렬된 데이터들로부터 인덱스를 통해 탐색하므로 효율적인 탐색이 가능해진다.

이제 우리는 인덱스를 통해 효율적인 탐색이 가능해진다는 것을 알았다.

바로 이 인덱스가 오늘 배워볼 주제이다.

어떻게 인덱스를 통해 효율적인 탐색이 가능하고, 어떻게 하면 효율적으로 인덱스를 사용할 수 있을 지 알아보자

1. 인덱스가 필요한 이유

테이블의 검색 성능을 높여주는 자료구조이다.

인덱스를 쓰게 되면 추가적인 쓰기 작업과 저장 공간을 활용하므로 탐색 속도를 높일 수 있다.

예시를 포함해서 지금까지의 설명으로 인덱스의 특징을 정리해볼 수 있다.

• 인덱스의 데이터는 정렬되어 있다.
• 인덱스는 추가적인 저장 공간을 필요로 한다.
• 인덱스를 사용해서 효율적인 탐색이 가능해진다.

여기까지만 들어도 인덱스가 무엇이고 어떤 장점이 있는 지 대략 파악되었을 것이다.

데이터베이스 쪽으로 좀 더 들어가서 구체적으로 왜 필요한 지 알아보자

2. 인덱스의 동작 방식

mySQL의 공식 문서를 보면 다음과 같이 나와있다.

Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows.

크게 두 가지로 요약할 수 있다.

1. 조건에 맞는 데이터를 빠르게 검색하기 위헤
2. 데이터를 빠르게 정렬하거나 그룹핑 하기 위해

예를 들어,

SELECT * FROM team WHERE name = ‘sehan’;

DELETE FROM logs WHERE datetime < ‘2023-06-16’;

UPDATE employee SET salary = salary * 1.5 WHERE id = 100;

SELECT * FROM team T JOIN department D ON [T.id](<http://T.id>) = D.id;

각각의 쿼리에는 조건들이 포함되어 있다.

따라서 해당 쿼리들이 실행되면 조건에 맞는 데이터들을 찾아야한다.

하지만 이 경우 테이블의 데이터가 중간이나 끝에 있다면 풀스캔을 해야하는 상황이 된다.

이를 보완하기 위해 인덱스는 별도의 자료구조 및 작업을 실행하여 테이블 탐색 성능을 향상시켜준다.

즉 테이블의 데이터, 조건들을 빠르게 찾기 위해 필요한 것이 인덱스이다.

또한 인덱스는 조인을 할 때 조인을 하기 위한 조건을 빠르게 찾기 위해 사용되기도 한다.

무조건 Select 에서만 필요한 것이 아닌 조건 탐색을 위해서든 단순 데이터 탐색을 위해서든 인덱스는 사용될 수 있다.

3. 인덱스의 종류

그렇다면 인덱스는 어떻게 동작할까?

인덱스의 자료구조

인덱스를 구현하기 위한 자료구조로는 크게 두가지가 있지만 , 대표적으로 B-tree 와 B+tree 가 있다.

마지막엔 추가로 해시에 대해서도 알아볼 것이다.

B-tree,B+tree 에서 ‘B’의 의미는 정확히 밝혀진 바는 없지만 균형을 맞춘다는 의미에서 Balanced 라는 의미로 통한다.

균형을 맞춤으로써 좀 더 빠른 인덱싱이 가능해진다.

만약 자식노드들이 Balanced 하지 않다면 어떻게 될까?

트리가 편향되어 있는 BST(이진 탐색 트리)모습을 상상해보자

BST는 균형을 맞추지 않기 때문에 위와 같은 모습이 나올 수 있다. 

최악의 경우에는 O(n)의 시간 복잡도가 나오는데 B tree는 트리의 균형을 맞춤으로써 시간 복잡도를 줄여준다.

이는 BST는 최대 2개의 자녀 노드를 가지지만 B tree는 여러개의 자녀노드를 가질 수 있기 때문에 가능하다.

B-Tree

B-tree 는 항상 데이터가 정렬되어 있다는 특징이 있다.

때문에 어떤 데이터를 탐색하더라도 O(logN)의 시간 복잡도를 가진다.

그리고 모든 리프 노드들은 같은 레벨에 있으며 따라서 Balanced 되었다 라고 할 수 있다.

B-tree의 구성을 살펴보자, 노드는 키값과 리프 노드에 대한 포인터로 구성되어 있다.

각 key들의 왼쪽 자식들은 key보다 작은 값 ,오른쪽 값은 key보다 큰 값으로 되어있다.

B-tree 구조의 데이터 탐색 과정을 알아보자

현재 데이터에서 정수 27 데이터를 찾아보려고 한다.

먼저 27은 31보다 작으므로 왼쪽 자식노드로 이동한다.

그 다음 11, 29와 데이터를 비교하게 되는데 이 중간값이라는 것을 알 수 있다.

따라서 가운데에 있는 자식 노드로 탐색을 하게되고 27을 발견하게 되면서 탐색이 끝난다.

이렇게 균형 있는 트리 구조를 통해 특정 데이터를 효율적으로 찾을 수 있다.

하지만 모든 경우에서 베스트인것은 아니다.

선형 탐색(Full scan)의 경우 모든 데이터를 다 탐색하므로 O(n)의 시간 복잡도를 가진다.

이 경우 뒤에서 살펴볼 B+tree 라는 것을 통해서 Full scan시 효율을 개선할 수 있다.

삽입

삽입의 경우 조회 방식과 통일하게 Leaf Node들을 탐색하고 노드 자리가 비어있다면 해당 자리에 노드를 삽입 , 꽉 차 있다면 노드를 분할해서 삽입한다.

예제를 통해 13 데이터를 넣을려고 한다고 가정해보자

탐색의 결과, 12와 14 사이의 값에 배정되었다. 하지만 해당 Leaf Node는 노드가 꽉 찬 상태이다.

따라서 부모 노드에 데이터를 넣어주었다.

이렇게 되면 부모 노드도 꽉 찬 상태가 되므로 중앙값인 11로 데이터를 분할해준다.

부모 노드에 11을 넣으니 또 노드가 꽉 찬 상태가 된다.

그러므로 다시 중앙값인 11로 데이터를 분할해준다.

이렇게 함으로써 삽입 과정이 완료되었다.

B-tree의 특징

1. 모든 자식 들을 같은 레벨에 존재한다.
2. 노드의 key의 수가 k개라면, 자식노드는 k+1 이다.
3. Key들은 항상 정렬된 상태이다.

여기까지가 B- Tree 에 대한 작동 과정이다.

이제 B+ Tree에 대해 알아보자

B + Tree

B- tree와의 가장 큰 차이점은 리프 노드들만 데이터를 가질 수 있다는 점이다.

이는 Full scan 시에 가장 명확한 장점을 가진다.

다시 B-tree 의 Full scan 과정을 생각해보자

B-tree에서는 Full scan을 하기 위해서 모든 브랜치 노드 및 자식 노드들을 탐색했어야했다.

하지만 B+tree에서의 Full scan 은 다르다.

그 이유는 Leaf Node 에만 데이터가 존재하고 이들은 연결 리스트로 연결되어 있기 때문이다.

덕분에 한번의 선형 탐색으로도 Full scan을 완료할 수 있다.

B+tree의 특징

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 효율적인 탐색이 가능하다.

해시

해시가 인덱스에서 사용되는 것을 알기전에 해시테이블에 대해 알 필요가 있다.

해시 테이블은 key값을 인자로 하는 해시 함수의 결과를 통해 인덱스를 만듦으로써 데이터를 저장하는 자료구조이다.

이 경우 찾고자 하는 데이터의 key값을 해시함수 한번으로 조회할 수 있으므로 O(1)의 시간 복잡도를 가진다.

하지만 해시 자료구조는 인덱스에서 거의 쓰이지 않는데, 그 이유는 등호 방식에만 최적화 되어있기 때문이다.

즉 DB 탐색 시에 주로 사용되는 범위검색이나 정렬에는 취약하다.

이러한 단점 때문에 인덱스에서는 많이 사용되지 않는다.

인덱스의 종류

클러스터 인덱스

클러스터 인덱스는 실제 데이터를 정렬하여 인덱스를 만드는 것이다.

따라서 테이블당 단 하나의 클러스터 인덱스만을 만들 수 있다.

실제 데이터를 통해서 인덱스를 만드는 것이므로 조회 과정에서 매우 빠른 속도를 가진다.

하지만 그 외 삽입 , 삭제 , 수정 같은 경우 클러스터 인덱스의 사용이 적합하지 않다.

(DML이 일어나는 경우 매번 정렬을 유지하기 때문)

따라서 클러스터 인덱스는 테이블의 수정이 빈번하지 않고 조회 위주의 작업을 하게 될 경우 좋은 효율을 가질 수 있다.

실생활에 비유해보면, 영어 단어 책을 예시로 들 수 있다.

영어 단어 책은 항상 A~Z 까지 정렬되있는 데 책 자체가 정렬되어 있는 이것을 클러스터 인덱스로 볼 수 있다 !

논클러스터 인덱스

실제 데이터 테이블을 정렬하지 않고 별도의 공간에 인덱스 페이지를 생성해서 저장하는 방식이다.

따라서 인덱스 페이지를 저장하기 위한 추가적인 메모리 공간이 필요하다.

DB에서 데이터를 저장하는 단위이다.

하나의 페이지는 16kb의 크기를 가진다.

MySQL :: MySQL 8.0 Reference Manual :: 15.11.2 File Space Management

논클러스터 인덱스는 데이터의 조회보다 수정,삭제,삽입 시에 더 좋은 효율을 가진다.

실생활에 비유해보면 ,

책 앞에 색인(인덱스)를 보고 해당 내용이 있는 페이지로 이동하는 것이다 !

따라서 데이터의 조회보단 수시로 데이터의 변경이 일어나는 테이블에서의 사용하는 것이 적합하다.

4. 인덱스 만드는 법

SQL 문을 통해 인덱스를 만들 수가 있다.

이 중에서는 우리가 흔히 쓰는 프라이머리 키를 통한 인덱스 생성도 포함되어있다.

위에서 두가지의 인덱스를 배웠는데 각각 어떻게 만드는 지를 알아보자

클러스터 인덱스

1. 프라이머리 키를 선언하는 경우
2. not null + 유니크 제약 조건을 선언하는 경우

ALTER TABLE member ADD CONSTRAINT id PRIMARY KEY(id); → 클러스터링

ALTER TABLE member ADD CONSTRAINT id UNIQUE NOT NULL; → 클러스터링

논 클러스터 인덱스

1. 유니크 제약 조건을 선언하는 경우
2. 직접 (유니크)인덱스를 생성하는 경우

ALTER TABLE member ADD CONSTRAINT name UNIQUE(name); → 논클러스터링

CREATE INDEX name ON member (name); → 논클러스터링

아니면 테이블을 생성할 때 인덱스를 생성할 수도 있다.

CREATE TABLE member(
id INT PRIMARY KEY,
name varchar(20) not null,
INDEX name_idx (name)
)

이처럼 여러가지 방식으로 DB 인덱스를 생성할 수 있다.

5. 적절한 인덱스 사용

인덱스를 쓰면 빠른 조회가 가능하다는 장점이 있지만 인덱스를 사용하게 될 경우 추가적인 작업이 발생하므로 상황에 따라 사용하는 것이 좋다. 그렇다면 인덱스가 굳이 필요없는 상황은 언제일까?

1. 인덱스의 범위가 너무 넓은 경우이다. 넓다는 것의 기준은 전체 데이터의 15%이상을 조회해야한다는 의미로 보면 적합하다.
2. 이 경우 인덱스를 통한 효과가 미미하기 때문에 인덱스의 사용을 지양한다.
3. 조회보다 삽입,삭제 등 수정 작업이 많을 경우이다. 이 경우도 마찬가지로 인덱스로 인한 효과가 미미하다.(수정 작업 시 where 로 조회하는 경우 제외)
4. 데이터 자체가 적은 경우는 배보다 배꼽이 더 큰 상황이 올 수 있기 때문에 사용을 지양하는 것이 좋다.

6. 언제 쓰면 좋을까?

카디널리티가 높은 데이터를 인덱스로 하면 효과적이다.

여기서 카디너리티란 사전적 의미로 그룹 내 요소의 개수를 의미한다.

그렇다면 카디널리티가 높다는 것은 어떤 걸 의미할까?

정해진 데이터 내에서 그룹 내 요소 개수가 많다는 것은 중복이 적다는 것이다.

중복이 적다는 것은 인덱스로 사용 시 매우 좋은 효율을 낼 수 있다.

예를 들어 중복된 데이터가 많은 성별 , 학년은 카디널리티가 낮으므로(중복이 높음) 인덱스에 적합하지 않다.

반대로 학번 , 고유 ID 등은 카디널리티가 높으므로(중복이 낮음) 인덱스 사용에 적합하다.

7. 결론

인덱스의 동작 방식과 인덱스의 사용 효과에 대해 알아보았다.

인덱스는 적절하게 사용하면 좋은 효율을 낼 수 있지만 상황에 맞지 않는 인덱스 사용은 오히려 역효과를 불러올 수 있다.

때문에 인덱스가 필요한 상황인 지를 잘 판단해 효율적으로 사용할 수 있어야한다.

참고 자료

DB Index 동작원리를 알아보자

클러스터 인덱스 vs 넌클러스터 인덱스 | zinirun

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

배경지식 : 함수 종속

두 튜플의 X값이 같다면 Y값도 같은 경우가 있다. 즉 X 값에 따라서 Y의 값이 결정되는 것인데, X와 Y를을 함수 종속 관계라고 한다.

관점에 따라서 X가 Y를 함수적으로 결정한다. 라고 할수도 있고 Y가 X에 함수적으로 의존한다. 라고 표현할 수도 있다.

이러한 관계를 함수 종속 혹은 Funtional Dependency(FD)라고 한다.

예를 들어 아래 테이블에서는 회원이름과 프로그램이 primary key이며 이는 가격을 결정한다.

(회원 번호가 좀 더 자연스럽지만 설명을 위해 다른 키를 예시로 든다.)

이 둘을 FD 관계라고 할 수 있으며 기호로는 {회원이름,프로그램} -> 가격 으로 표시한다.

여기서 주의할 점은 FD를 파악할때는 스키마의 의미를 보고 파악해야하며 테이블의 데이터들을 보고 추론해서는 안된다.

왜냐하면 회원 이름과 가격 데이터가 FD처럼 보인다고 생각해도 동명이인이라는 변수가 있을 수 있고 여러 예외 상황들이 있기 때문이다.

이렇게 구축하려는 데이터베이스의 속성(애트리뷰트)가 관계적으로 어떤 의미를 지닐지에 따라서 FD들이 달라진다.

따라서 데이터(or state)만 보고 판단하기보단 스키마를 보고 의미적으로 존재하는 지 파악해야한다.

또 한가지 중요한 점은 FD는 역관계가 성립하지 않는다는 것이다.

X -> Y 관계라고 해서 Y->X가 성립하지는 않는다. 예를 들어보면 프로그램이 가격을 결정짓는 다고 해서 가격이 프로그램을 결정하는 것은 아니다!

{프로그램} -> 가격 (O)
{가격} -> 프로그램 (X)

*{}-> Y 는 "Y은 언제나 하나의 값만을 가진다"는 의미이다.

Trivial Funtional Dependcy

X -> Y의 관계에서 Y가 X의 부분 집합이라면 이 관계를 Trivial Funtional Dependcy라고 한다.

예를 들어, {a,b,c} -> {c} 같이 c가 a,b,c의 부분집합인 경우가 있다. 

반대의 경우로는 당연히 non-Trivial Funtional Dependcy (아예 안겹치면 completely-non) 같은 관계가 있다.

Partial Functional Dependency

X->Y의 관계에서 X의 부분집합(전체를 제외한)만으로 Y를 결정지을 수 있다면 이를 Partial Functional Dependency라고 한다.

예를 들어, {a,b,c} -> {c} 에서 {a} -> {c}가 성립하는 경우가 있다. 반대의 경우는 Full Funtional Dependcy가 있다.

DB 정규화란

데이터 중복과 insertion , update , deletion anomaly를 최소화하기 위해 함수의 종속성을 이용해서 relational DB를 구성하는 과정이다.

삽입이상 : 자료를 삽입할 때 의도치 않은 자료까지 삽입해야한다. (ex. null)

갱신이상 : 중복된 데이터 중 일부만 수정되어 모순이 발생하는 것이다.

삭제이상 : 어떤 정보를 삭제하면 의도치 않은 다른 정보까지 삭제된다.

정규화를 진행하게 되면 데이터 수정 시에 여러 이상 현상들을 줄일 수 있고, 확장에 용이하여 데이터 구조가 변경되어도 어플리케이션에 최소한의 영향만을 미친다.

정규형에는 몇 단계의 nf(normal forms)가 있는데 처음 단계부터 순차적으로 진행하며 앞 단계를 만족해야 다음 단계를 진행할 수 있다.

보통 실무에서 3nf까지 하면 정규화되었다라고 말한다.

제 1 정규형(1NF)

모든 attribute의 value는 더 이상 나눠질 수 없는 값이어야한다. -> 여러 값을 가지고 있으면 안된다.

(예시 참고: 코딩애플)

영희에 해당하는 프로그램 데이터가 두 개를 가지고 있으므로 이는 제 1 정규형을 위반한다.

제 2 정규형(2NF)

모든 non-prime attribute는 모든 key에 대해 full funtional dependent해야한다.
(현재 테이블과 상관없는 컬럼들을 분리한다.)

제 1 정규형을 적용하였으면 이제 제 2 정규형을 진행할 차례이다.

현재 테이블에서는 회원 정보와 프로그램 정보가 혼재해있다. 이런 테이블 구조는 데이터를 변경해야할 시에 매우 번거로울 수 있다.

(예시 참고: 코딩애플)

예시에서는 가격 컬럼이 프로그램에 partial funtional dependent하다.

{회원이름,프로그램} -> 가격

{프로그램} -> 가격

primary key가 회원번호,프로그램이지만 가격은 프로그램 하나만으로 결정될 수 있다. -> 현재 테이블에 상관 없는 데이터가 들어간 것이다!

이 상황에서 가격이 변경됨에 되면 컬럼을 일일이 수정해주어야 하기 때문에 매우 비효율적이다. 따라서 다음과 같이 분리할 수 있다.

이제 가격은 프로그램에 full functional dependency하며 프로그램 테이블에 연관있는 컬럼들만 들어가 있다.

만약 가격이 수정된다고 하더라도 이 테이블의 값만 수정하면 되기 때문에 효율적이라고 할 수 있다.

제 3 정규형 (3NF)

모든 non-prime attribute(키를 제외한)는 어떤 key에도 transitive FD(이행적 함수 종속) 하면 안된다.

transitive FD(이행적 함수 종속) 이란, X -> Y 이고 Y -> Z이면 X -> Z 인 경우이다.

이 경우에는 프로그램을 통해 강사가 결정되는데 동시에 강사가 전화번호 또한 결정할 수 있다.

프로그램 -> 강사 

강사  -> 전화번호

=> 프로그램 -> 전화번호 같은 이행적 함수 종속이 발생한다.

다음과 같은 문제가 발생할 수 있다. 예를 들어 강사가 여러 개의 과목을 담당한다고 가정하였을 때 중복된 강사는 여러 개일 것이다.

그렇다면 만약 해당 강사가 전화번호를 변경하였을 경우 일일이 변경해주어야 하며 이는 갱신 이상이 발생할 수 있다.

따라서 다음과 같이 해당 컬럼을 분리해줌으로써 문제를 해결할 수 있다.

보통 여기까지 오면 정규화 되었다고 말할 수 있지만 BCNF까지만 더 알아보려고 한다.

BCNF

모든 유효한 non-trivial FD X -> Y 는 X가 슈퍼키여야한다.

만약 테이블에 강의실 정보까지 추가되었다고 가정해보자 

이제 강의실을 통해 해당 강사의 정보를 알 수 있다. 하지만 굳이 중복된 강사의 데이터들을 가지고 있어야할까? 라는 의문이 드는데 이와 관련된 개념이 BCNF이다.

테이블을 보면 강의실을 통해 현재 어떤 강사가 배정되었는 지 알 수 있으므로 강의실 -> 강사는 non-trivial FD 라고 할 수 있다.

하지만 강의실은 슈퍼키가 아니므로 BCNF를 위반한다.

테이블을 분리한 결과 강의실은 슈퍼키가 되었고 더 이상 원래 테이블에 중복된 강사 데이터를 넣지 않아도 된다.

이렇게 해두면 BCNF를 지키면서 중복된 데이터들을 최소화 할 수 있다.