정규화 & 이상현상 & 인덱스

이상현상

잘못된 테이블 설계로 데이터를 삽입, 삭제, 수정할 때 논리적으로 생기는 오류를 말한다. 데이터의 중복이 발생하고 전체적인 무결성이 저하된다. 이 이상현상으로 인해 현실세계의 실제 값과 데이터베이스에 저장된 값이 일치하지 않는 문제가 발생한다.

위 DB를 예시로 이상현상의 종류를 설명할 것이다!

삽입 이상

자료를 삽입할 때 의도하지 않은 자료까지 삽입해야만 자료를 테이블에 추가할 수 있는 현상이다.
위 DB에서 강의를 아직 수강하지 않은 학생을 삽입할 경우 강의 코드와 강의명 속성에는 null 값이 들어가야 하는 문제가 생긴다!

갱신 이상

중복된 데이터 중 일부만 수정되어 데이터 모순이 일어나는 현상이다.
위 DB에서 강의 코드가 AC3인 김현수의 전화번호를 수정할 경우, 3번째 튜플의 데이터만 수정될 것이다. 그렇게 된다면 3, 4번째 튜플은 같은 사용자의 데이터임에도 불구하고 전화번호가 다르게 된다!

삭제 이상

어떤 정보를 삭제하면, 의도하지 않은 다른 정보까지 삭제되어버리는 현상이다.
위 DB에서 강의 코드가 AC1인 데이터베이스 개론 강의를 삭제하게 되면, 이태호 학생의 데이터까지 삭제되어 버린다!

정규화

데이터베이스 정규화란 관계형 데이터베이스 데이터 모델의 중복을 최소화하고 데이터의 일관성, 유연성을 확보하기 위한 목적으로 데이터를 분해하는 과정을 뜻한다. 보통 이상현상이 존재하는 경우 릴레이션을 분해하여 이상현상을 없애기 위해 사용된다. 정규형이 높아질수록 이상현상은 줄어들게 된다.

정리

• 불필요하거나 중복되는 데이터들을 제거함
• 이상 현상을 방지함
• 데이터 저장을 논리적으로 함 (테이블의 구성을 논리적이고 직관적이게 함)

정규화는 1 정규화부터 6 정규화까지 여러 과정이 존재하지만, 실제로는 보통 1 ~ 3 정규화까지의 과정을 거치게 된다고 한다!

제 1 정규화

제 1 정규화(1NF)란 테이블의 컬럼이 원자값을 갖도록 테이블을 분해하는 것이다.

위 예시에서 추신수와 박세리는 원자값을 가지고 있지 않는다. 따라서 제 1 정규형을 만족하지 않는다.

이를 분해해주면 위와 같이 된다.

제 2 정규화

제 2 정규화(2NF)란 제 1 정규화를 진행한 테이블에 대해 완전 함수 종속을 만족하도록 테이블을 분해하는 것이다. 여기서 완전 함수 종속이라는 것은 기본키의 부분집합이 결정자가 되어선 안된다는 것을 의미한다. (부분적 종속이 없어야 함)

위 테이블에서 기본키는 (학생번호, 강좌이름)으로 복합키이다.
성적은 학생번호와 강좌이름이 함께 있을때에만 결정될 수 있지만 강의실 같은 경우에는 강좌이름만 있어도 충분히 결정될 수 있다.
그렇기 때문에 부분적 종속 부분을 떼어 하나의 테이블로 만들어주면 된다!

분해해주면 이런식으로 된다.

제 3 정규화

제 3 정규화(3NF)란 제 2 정규화를 진행한 테이블에 대해 이행적 함수 종속을 없애도록 테이블을 분해하는 것이다.
이행적 함수 종속이란 A -> B, B -> C가 성립할 때, A -> C가 성립되는 것을 의미한다.

위 테이블에서 학생 번호는 강좌 이름을 결정하고 있고, 강좌 이름은 수강료를 결정하고 있다. 그런데, 학생 번호가 수강료 또한 결정하고 있다. (사실 결정이라기 보다는 구분한다는 말이 맞는 것 같다.) 따라서 이행적 함수 종속이 존재하고, 이를 없애면 제 3 정규화를 만족하게 된다.
없애는 방법은 A와 B를 한 테이블로, B와 C를 한 테이블로 만들어 주는 것이다. 따라서 위의 예시에서는 학생 번호와 강좌 이름을 한 테이블로, 강좌 이름과 수강료를 한 테이블로 분해하면 된다.

BCNF 정규화

BCNF 정규화란 제 3 정규화를 진행한 테이블에 대해 모든 결정자가 후보키가 되도록 테이블을 분해하는 것이다.

위 테이블에서 기본키는 (학생번호, 특강이름)으로 복합키이다. 이 키는 교수를 결정하고 있는데, 교수는 또 특강 이름을 결정하고 있다. 교수가 특강 이름을 결정하는 결정자이지만 후보키는 아니라는 점이 문제이다. 이를 해결해야 BCNF를 만족시킬 수 있기 때문에 모든 결정자는 항상 후보키가 되도록 릴레이션을 분해해주면 된다.

분해한 결과를 위와 같다.

인덱스

인덱스란?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕는다.
인덱스는 데이터베이스 내의 특정 컬럼이나 컬럼들의 조합에 대한 값과 해당 값이 저장된 레코드의 위치를 매핑하여 데이터베이스 쿼리의 성능을 최적화하는데에 중요한 역할을 한다!

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

인덱스의 관리

인덱스는 항상 최신 데이터를 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 따라서 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음의 연산을 추가적으로 해줘야 한다. (이에 따른 오버헤드가 발생한다.)

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

인덱스의 장단점

장점

1. 검색 대상 레코드의 범위를 줄여 검색 속도를 빠르게 할 수 있다.
2. 중복 데이터를 방지하거나 특정 컬럼의 유일성을 보장할 수 있다.(UNIQUE index 사용시에)
3. ORDER BY 절과 GROUP BY 절, WHERE 절 등이 사용되는 작업이 더욱 효율적으로 처리된다. (이미 정렬되어 있어 빠르게 조건을 찾을 수 있음)

단점

1. 인덱스 생성에 따른 추가적인 저장 공간이 필요하다.
2. INSERT, DELETE, UPDATE 작업 시에도 인덱스를 업데이트해야 하므로 성능 저하가 발생할 수 있다.
3. 한 페이지를 동시에 수정할 수 있는 병행성이 줄어든다.
4. 인덱스 생성 시간이 오래 걸릴 수 있다.

인덱스를 사용하는 경우

1. 대량의 데이터를 검색하는 경우
   대량의 데이터를 검색해야 하는 경우에는 인덱스를 사용하여 검색 속도를 향상시킬 수 있다. 대량의 데이터를 전체 스캔하는 것은 매우 느리고 부하가 발생하기 때문에 이 경우에 인덱스를 사용하여 검색하는 것이 효율적이다.
2. 정렬된 결과를 출력하는 경우
   인덱스를 사용하여 데이터를 정렬하면 매우 빠르게 정렬된 결과를 출력할 수 있다. 따라서 데이터를 정렬하는 경우에는 인덱스를 사용하는 것이 좋다.
3. 조인 연산을 수행하는 경우
   조인 연산을 수행하는 경우에는 인덱스를 사용하여 연산 속도를 향상시킬 수 있다. 인덱스를 생성하여 조인 대상 테이블의 데이터를 빠르게 검색하는 것이 좋다.
4. 유니크한 값을 가져오는 경우
   인덱스는 유니크한 값을 가지고 있는 필드에 대해 중복되지 않는 값을 빠르게 검색할 수 있다. 이러한 경우 인덱스를 사용해 검색 속도를 빠르게 할 수 있다.
5. 검색 빈도가 높은 경우
   검색 빈도가 높은 필드에 대해서 인덱스를 생성하여 검색 속도를 향상시키는 것이 좋다.

인덱스의 알고리즘

탐색 시간이 가장 빠른 해시 테이블을 사용하지 않는 이유

만약 단 하나의 데이터를 탐색하기만 하면 된다면 당연히 해시테이블이 효율적이겠으나 DB에서는 등호 뿐 아니라 부등호도 사용할 수 있다. 모든 값이 정렬되어있지 않으므로, 해시 테이블에서는 특정 기준보다 크거나 작은 값을 찾는 것은 시간 복잡도를 보장할 수 없고 매우 비효율적이다. 따라서 기준값보다 크거나 작은 요소들을 항상 탐색할 수 있어야 하는 DB 인덱스 용도로 해시 테이블은 어울리지 않는 자료구조이다.

RedBlack-Tree VS B-Tree

• RedBlack-Tree
  각 노드는 하나의 값만 가진 상태로 좌, 우 자식 노드의 개수 밸런스를 맞추는 Tree이다.
• B-Tree
  노드 하나에 여러 데이터가 저장될 수 있다. 각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다.
• 공통점
  두 트리는 항상 좌, 우 자식노드 개수의 밸런스를 유지하므로 최악의 경우에도 무조건 탐색 시간이 O(logN)을 가지게 된다.

그럼에도 불구하고 RedBlack-Tree가 선택받지 못한 이유

이 두 트리의 가장 큰 차이는 하나의 노드가 가지는 데이터의 개수이다. RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터 요소만을, B-Tree는 하나의 노드에 여러 개의 데이터 요소를 저장한다.
하나의 노드에 여러 개의 데이터 요소를 저장할때 B-Tree에서는 마치 배열처럼 저장한다. 실제 메모리 상에 차례대로 저장이 되어있는 것이다. 같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다. 같은 노드 상 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 하는 것이다.
반면 RedBlack-Tree는 데이터에 접근할 때 무조건 참조 포인터로 접근을 하게 된다. 이론적인 시간 계산 방식인 시간 복잡도는 O(logN)으로 변하지 않으나 물리적이고 절대적인 시간 개념으로는 배열 접근이 훨씬 빠를 수 밖에 없다!

결론적으로 참조 포인터 접근의 수 때문에 같은 밸런스 트리임에도 RedBlack-Tree를 사용하지 않는 것이다.

데이터 접근이 빠른 배열이 선택받지 못한 이유

배열이 B-Tree보다 빠른 것은 탐색뿐이기 때문이다. 배열 내에서 데이터 저장, 삭제가 일어나는 순간 B-Tree보다 훨씬 비효율적인 성능이 발생하게 된다. 새로운 데이터 저장시에나 삭제시에 모든 데이터를 한 칸씩 이동해야 하기 때문이다.

B-Tree가 가장 적합한 이유

1. 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제 X
2. 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능
3. 데이터 탐색 뿐 아니라 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가짐

참고

https://dev-coco.tistory.com/62
https://mangkyu.tistory.com/110
https://rebro.kr/160
https://mangkyu.tistory.com/96
https://ittrue.tistory.com/331
https://lob-dev.tistory.com/entry/Week01-%EB%B8%94%EB%9E%99%EC%BB%A4%ED%94%BC-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EC%8A%A4%ED%84%B0%EB%94%94