정규화란? DB 인덱스란?

1. 정규화(Normalization)란?

정규화(Normalization)의 기본 목표는 테이블 간에 중복된 데이터를 허용하지 않는다는 것이다. 중복된 데이터를 허용하지 않음으로써 무결성(Integrity)(=정확성)를 유지할 수 있으며, DB의 저장 용량 역시 줄일 수 있다.

이러한 테이블을 분해하는 정규화 단계가 정의되어 있는데, 여기서 테이블을 어떻게 분해되는지에 따라 정규화 단계가 달라지는데, 각각의 정규화 단계에 대해 자세히 알아보도록 하자.

 

1-1.  제1 정규화

제1 정규화란 테이블의 컬럼이 원자값(Atomic Value, 하나의 값)을 갖도록 테이블을 분해하는 것이다. 예를 들어 아래와 같은 고객 취미 테이블이 존재한다고 하자. 

 

 

위의 테이블에서 추신수와 박세리는 여러 개의 취미를 가지고 있기 때문에 제1 정규형을 만족하지 못하고 있다. 이럴 경우 예를 들어 추신수의 음악취미를 없애고 싶은 경우 원치 않게 추신수의 영화취미까지 사라질 수 있다(삭제이상).그렇기 때문에 이를 제1 정규화하여 분해할 수 있다. 제1 정규화를 진행한 테이블은 아래와 같다.

 

 

1-2. 제2 정규화 

제2 정규화란 제1 정규화를 진행한 테이블에 대해 완전 함수 종속을 만족하도록 테이블을 분해하는 것이다. 여기서 완전 함수 종속이라는 것은 기본키의 부분집합이 결정자가 되어선 안된다는 것을 의미한다.
예를 들어 아래와 같은 수강 강좌 테이블을 살펴보자. 

 

 

 

이 테이블에서 기본키는 (학생번호, 강좌이름)으로 복합키이다. 그리고 (학생번호, 강좌이름)인 기본키는 성적을 결정하고 있다. (학생번호, 강좌이름) --> (성적)
그런데 여기서 강의실이라는 컬럼은 기본키의 부분집합인 강좌이름에 의해 결정될 수 있다. (강좌이름) --> (강의실)

이럴 경우 데이터베이스 수업의 강의실이 공학관 112호로 바뀌었다고 해보자. 이를 위해서는 강의실 갱신을 두번 바꿔줘야 하는데 이 과정에서 무결성이 깨질 수 있다(어떤 것은 바뀌고 어떤 것은 안바뀌고).
즉, 기본키(학생번호, 강좌이름)의 부분키인 강좌이름이 결정자이기 때문에 위의 테이블의 경우 다음과 같이 기존의 테이블에서 강의실을 분해하여 별도의 테이블로 관리하여 제2 정규형을 만족시킬 수 있다.

 

 

 

 

1-3. 제3 정규화

제3 정규화란 제2 정규화를 진행한 테이블에 대해 이행적 종속을 없애도록 테이블을 분해하는 것이다. 여기서 이행적 종속이라는 것은 A -> B, B -> C가 성립할 때 A -> C가 성립되는 것을 의미한다.
예를 들어 아래와 같은 계절 학기 테이블을 살펴보자. 

 

 

 

 

기존의 테이블에서 학생 번호는 강좌 이름을 결정하고 있고, 강좌 이름은 수강료를 결정하고 있다. 그렇기 때문에 이를 (학생 번호, 강좌 이름) 테이블과 (강좌 이름, 수강료) 테이블로 분해해야 한다. 

이행적 종속을 제거하는 이유는 비교적 간단하다. 예를 들어 501번 학생이 수강하는 강좌가 스포츠경영학으로 변경되었다고 하자. 이행적 종속이 존재한다면 501번의 학생은 스포츠경영학이라는 수업을 20000원이라는 수강료로 듣게 된다. 물론 강좌 이름에 맞게 수강료를 다시 변경할 수 있지만, 이러한 번거로움을 해결하기 위해 제3 정규화를 하는 것이다.
즉, 학생 번호를 통해 강좌 이름을 참조하고, 강좌 이름으로 수강료를 참조하도록 테이블을 분해해야 하며 그 결과는 다음의 그림과 같다.

 

 

1-4. BCNF 정규화 

BCNF 정규화란 제3 정규화를 진행한 테이블에 대해 모든 결정자가 후보키가 되도록 테이블을 분해하는 것이다. 예를 들어 다음과 같은 특강수강 테이블이 존재한다고 하자.

 

 

 

 

특강수강 테이블에서 기본키는 (학생번호, 특강이름)이다. 그리고 기본키 (학생번호, 특강이름)는 교수를 결정하고 있다. 또한 여기서 교수는 특강이름을 결정하고 있다. 그런데 문제는 교수가 특강이름을 결정하는 결정자이지만, 후보키가 아니라는 점이다. 이런 경우 김교수의 강의가 컴퓨터 과학으로 바뀌었다면 김교수 강의는 두번에 걸쳐 수정이 있어야 하지만 이 과정에서 무결성이 깨질 수 있다.
그렇기 때문에 BCNF 정규화를 만족시키기 위해서 위의 테이블을 분해해야 하는데, 다음과 같이 특강신청 테이블과 특강교수 테이블로 분해할 수 있다.

 

 

1-5. 정규화 장단점

장점: 각종 이상 현상들을 해결할 수 있다. 

단점: 릴레이션의 분해로 인해 릴레이션간의 연산이 많아져 응답 시간이 오히려 느려질 수도 있는 단점

 

2. 인덱스란?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.

데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.

 

 

 

인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 그러한 이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.

만약 index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. Full Scan은 전체를 비교하여 탐색하기 때문에 처리 속도가 떨어진다.

 

 

2-1. 인덱스(index)의 관리

DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.

• INSERT: 새로운 데이터에 대한 인덱스를 추가함
• DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
• UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

 

2-2. 인덱스(index)의 장점과 단점 

• 장점
  • 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
  • 전반적인 시스템의 부하를 줄일 수 있다.
• 단점
  • 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
  • 인덱스를 관리하기 위해 추가 작업이 필요하다.
  • 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. 그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문이다. 앞에서 설명한대로, UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 하였다. 만약 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다. 

 

 

2-3. 인덱스(index)를 사용하면 좋은 경우

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼(왜냐하면 이미 데이터가 인덱스에 따라 정렬되어 있기 때문에)
• 데이터의 중복도가 낮은 컬럼
• 기타 등등

인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그러므로 사용되지 않는 인덱스는 바로 제거를 해주어야 한다. 

 

 

 

2-4. 인덱스(Index)의 자료구조

인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데, 가장 대표적인 해시 테이블과 B-Tree, B+Tree에 대해서 알아보도록 하자.

 

2-4-1. 해시테이블

모든 자료구조와 그 어떤 알고리즘을 비교해도 탐색 시간이 가장 빠른 것은 바로 해시 테이블이다. 해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근을 하기 때문에 O(1)이라는 시간 복잡도를 가진다. (물론 해시 충돌 등으로 최악의 경우에 O(N)이 될 수 있지만, 평균적으로는 O(1)으로 볼 수 있다)

그러나 이는 온전히 '단 하나의 데이터를 탐색하는 시간' 에만 O(1)이다. 예를 들어 1,2,3,4,5가 저장되어 있는 해시 테이블에서 3이라는 데이터를 찾을 때에만 O(1)이라는 것이다. (3이라는 데이터를 인풋으로 해시 함수를 통해 나온 해시 값으로 3이 저장된 메모리 공간에 접근을 할 것이기 때문이다)

'그게 무엇이 문제이냐'라고 생각한다면 잠깐 이 부분을 놓쳤을 것이다.

 

우리는 DB에서 등호(=) 뿐 아니라 부등호(<, >)도 사용할 수 있다는 것을.

 

모든 값이 정렬되어있지 않으므로, 해시 테이블에서는 특정 기준보다 크거나 작은 값을 찾을 수 없다. 굳이 찾으려면 찾을 수는 있지만 O(1)의 시간 복잡도를 보장할 수 없고 매우 비효율적이다.

그렇기에 기준 값보다 크거나 작은 요소들을 항상 탐색할 수 있어야 하는 DB 인덱스 용도로 해시 테이블은 어울리지 않는 자료구조인 것이다.

 

2-4-2. B-Tree

B-Tree는 위처럼 노드 하나에 여러 데이터가 저장될 수 있다. 각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. 그러므로 자식 노드 개수는 (n+1)을 가진다. 

 

이처럼, 위 두 개의 트리는 항상 좌, 우 자식노드 개수의 밸런스를 유지하므로 최악의 경우에도 무조건 탐색 시간이 O(logN)을 가지게 된다.

 

2-4-3. B+Tree

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+Tree는 모든 노드에 데이터(Value)를 저장했던 B-Tree와 다른 특성을 가지고 있다.

• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
• 리프노드들은 LinkedList로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다. 이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

이러한 이유로 비록 B+Tree는 O(log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

 

 

 

 

 

 

 

https://mangkyu.tistory.com/110

[Database] 정규화(Normalization) 쉽게 이해하기

http://www.tcpschool.com/mysql/mysql_intro_relationalDB#:~:text=%EC%9D%B4%EC%B2%98%EB%9F%BC%20%EB%8D%B0%EC%9D%B4%ED%84%B0%EC%9D%98%20%EC%A2%85%EC%86%8D%EC%84%B1%EC%9D%84,%ED%95%98%EB%8A%94%20%EA%B0%92%EC%9D%84%20%EA%B0%80%EC%A7%91%EB%8B%88%EB%8B%A4.

코딩교육 티씨피스쿨

https://mangkyu.tistory.com/96

[Database] 인덱스(index)란?

https://helloinyong.tistory.com/296

데이터베이스 인덱스는 왜 'B-Tree'를 선택하였는가

https://rebro.kr/160

[DB] 8. 정규형 (1NF, 2NF, 3NF, BCNF)

https://rebro.kr/159#:~:text=%EC%9D%B4%EC%83%81%ED%98%84%EC%83%81%EC%9D%B4%EB%9E%80%2C%20%ED%85%8C%EC%9D%B4%EB%B8%94%20%EB%82%B4%EC%9D%98,%ED%98%84%EC%83%81%EB%93%A4%EC%9D%84%20%ED%95%B4%EA%B2%B0%ED%95%A0%20%EC%88%98%20%EC%9E%88%EB%8B%A4.

[DB] 7. 정규화 & 함수 종속성 & 이상현상

https://ssup2.github.io/theory_analysis/B_Tree_B+_Tree/

B-Tree, B+ Tree