- DB Key
- JOIN
- Index
- Normalization
- Anomaly
Key
키(Key)는 데이터베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 다른 튜플들과 구별할 수 있는 유일한 기준이 되는 Attribute(속성)이다.
튜플: 릴레이션을 구성하는 각각의 행, 속성의 모임으로 구성된다. 파일 구조에서는 레코드와 같은 개념. 튜플의 수 = 카디널리티(Cardinality) = 기수 = 대응수
1. Candidate Key (후보키)
- 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별할 수 있는 속성들의 부분집합을 의미한다.
- 모든 릴레이션은 반드시 하나 이상의 후보키를 가져야 한다.
- 릴레이션에 있는 모든 튜플에 대해서 유일성과 최소성을 만족시켜야 한다.
1. 유일성: Key로 하나의 Tuple을 유일하게 식별할 수 있음
2. 최소성: 꼭 필요한 속성으로만 구성
ex) <학생> 릴레이션에서 '학번' 이나 '주민번호' 는 다른 레코드를 유일하게 구별할 수 있는 기본키로 사용할 수 있으므로 후보키가 될 수 있다. 즉 기본키가 될 수 있는 키들을 후보키라고 한다.
2. Primary Key (기본키)
- 후보키 중 선택한 Main Key
- 한 릴레이션에서 특정 튜플을 유일하게 구별할 수 있는 속성이다.
- Null 값을 가질 수 없다. (개체 무결성의 첫번째 조건)
- 기본키로 정의된 속성에는 동일한 값이 중복되어 저장될 수 없다. (개체 무결서의 두번째 조건)
ex) <학생> 릴레이션에는 '학번' 이나 '주민번호' 가 기본키가 될 수 있고, <수강> 릴레이션에는 '학번' + '과목명' 으로 조합해야 기본키가 만들어 질 수 있다. 왜냐하면 <수강> 릴레이션에서는 '학번' 속성과 '과목명' 속성 개별적으로는 다른 튜플들과 구별되지 않기 때문에 기본키로 사용할 수 없다.
ex2) <학생> 릴레이션에서 '학번' 을 기본키로 정의하면 이미 입력된 '1001'은 다른 튜플의 '학번' 속성 값으로 입력할 수 없다.
3. Alternate Key (대체키)
- 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키들을 말한다.
- 보조키라고도 한다.
ex) <학생> 릴레이션에서 '학번'을 기본키로 정의하면 '주민번호'는 대체키가 된다.
4. Super Key (슈퍼키)
- 유일성은 만족하지만, 최소성은 만족하지 못하는 키
5. Foreign Key (외래키)
- 다른 릴레이션의 기본키를 그대로 참조하는 속성의 집합
Index
인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.
Index는 테이블 내 1개의 컬럼 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다.
만약 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아 보는 것은 오랜 시간이 걸린다. 그렇게 때문에 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.
DB의 특정 테이블에서 원하는 데이터들을 조회할 때, 조건절에 사용하는 컬럼의 Index가 없다면 어떻게 될까? 책의 사례와 유사하게, 원하는 데이터의 위치를 특정할 힌트가 없다보니 테이블 전체를 탐색 (Full Scan)하게 된다. 테이블에 데이터의 양이 많아질수록 검색에 소요되는 시간이 길어진다.
이처럼 데이터베이스에서 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.
Index는 데이터의 주소값을 저장하는 별도의 특별한 자료 구조이다. USER 테이블의 COMPANY_ID 컬럼에 대한 Index가 존재한다면, 예시 쿼리를 수행할 때 테이블 전체를 탐색하지 않고 해당 Index를 바탕으로 원하는 데이터의 위치를 빠르게 검색한다. Index는 테이블에 있는 하나 이상의 컬럼으로 생성이 가능하다.
인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 함께 향상된다. 그러한 이유는 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.
만약 Index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. Full Scan은 전체를 비교하여 탐색하기 때문에 처리 속도가 떨어진다.
성능 테스트
User.java
IndexTest.java
- 100만건의 데이터가 존재할 때, 원하는 데이터를 조회하는데 걸리는 시간을 측정하는 테스트 예제이다.
- 테스트 환경에 따라 검색 성능이 적게는 2배에서 많게는 4배 차이가 났다.
- Index 적용 전에는 약 0.22초가 소요된 것을 확인할 수 있다.
- Index 적용 이후에는 약 0.12초가 소요된 것을 확인할 수 있다.
인덱스(index)의 관리
DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.
- INSERT: 새로운 데이터에 대한 인덱스를 추가함
- DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함
- UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함
인덱스의 장점과 단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다. 그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문인데, DELETE와 UPDATE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음'처리를 해준다고 했다. 만약 어떤 테이블에 DELETE와 UPDATE가 빈번하게 발생한다면 실제 데이터는 10만건이지만 인덱스는 100만건이 넘어가게 되어, SQL문 처리시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 수도 있다.
인덱스를 사용하면 좋은 경우
- 규모가 작지 않은 테이블
- INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
- JOIN이나 WHERE 또는 ORDER BY가 자주 사용되는 컬럼
- 데이터의 중복도가 낮은 컬럼
인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그러므로 사용되지 않는 인덱스는 바로 제거를 해주어야 한다.
인덱스의 자료구조
인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데, 가장 대표적인 Hash Table과 B+ Tree에 대해서 알아보도록 하겠다.
해시 테이블 (Hash Table)
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
해시 테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현하였다.
해시 테이블은 내부에 버켓이라고 하는 배열이 존재한다. 해시 함수를 통해 Key를 고유한 해시 값으로 변환시키는데, 이를 버켓 배열의 인덱스로 사용하며 해당 인덱스에 Value를 저장한다. Key값으로 Value가 저장되어 있는 위치(주소)를 바로 산출할 수 있기 때문에, 해시 테이블의 평균적인 시간 복잡도는 O(1)이며 매우 빠른 검색을 지원한다. 하지만 해시 함수를 제대로 정의하지 않으면 해시 함수를 통해 산출한 해시 값이 중복되는 해시 충돌이 발생한다. 너무 많은 해시 충돌이 발생하면 검색 성능이 하락해서 시간 복잡도가 O(N)에 수렴할 수 있다.
아울러 DB 인덱스에서 해시 테이블이 사용되는 경우는 제한적인데, 그러한 이유는 해시가 등호(=) 연산에만 특화되었기 때문이다. 해시 함수는 값이 조금이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.
즉, 예를 들면 "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못하게 된다. 이러한 이유로 데이터베이스의 인덱스에서는 B+ Tree가 일반적으로 사용된다.
B-Tree
B-Tree란 자식 노드가 2개 이상인 트리를 의미한다. 이진 검색 트리처럼 각 Key의 왼쪽 자식은 항상 Key보다 작은 값을, 오른쪽 자식은 큰 값을 가진다. B-Tree 기반의 DB Index는 특정 컬럼의 값(Key)에 해당하는 노드에 데이터의 위치(Value)를 저장한다.
B-Tree의 Key-Value 값들은 항상 Key를 기준으로 오름차순 정렬이다. 이로 인해 부등호 연산 (>, <)에 대해 해시 테이블보다 효율적인 데이터 탐색이 가능하다. 또한, B-Tree는 균형트리로서, 최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일하기 때문에 평균 시간 복잡도는 O(logN)이다.
그러나 Index가 적용된 테이블에 데이터 갱신(INSERT, UPDATE, DELETE)이 반복되다보면, 트리의 균형이 깨지면서 성능이 악화된다.
또한 DB Index 컬럼은 부등호 (>, <)를 이용한 순차 검색 연산이 자주 발생한다. B-Tree가 해시 테이블보다 부등호를 이용한 검색 연산 성능이 좋지만, 순차 검색의 경우 중위 순회를 하기 때문에 효율이 좋지 않다. 예시의 경우 7 > 3 > 8 > 1 > 9 > 4 > 10 > 0 > 11 > 5 > 2 > 6 순으로 조회하는 등 상당히 많은 노드를 확인해야 한다.
이러한 이유로 MySQL 엔진인 InnoDB는 B-Tree를 확장 및 개선한 B+Tree를 Index의 자료구조로 사용한다.
B+ Tree
B+ Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B- Tree를 개선시킨 자료구조이다. B+ Tree는 모든 노드에 데이터(Value)를 저장했던 B- Tree와 다른 특성을 가지고 있다.
- 리프노드 (데이터 노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드 (인덱스 노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
- 리프노드들은 LinkedList로 연결되어 있다.
- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.
말단의 리프 노드에만 데이터의 위치(Value)를 관리하기 때문에 중간 브랜치 노드에 Value가 없어서 B-Tree보다 메모리를 덜 차지하는 만큼, 노드의 메모리에 더 많은 key를 저장할 수 있다. 아울러 하나의 노드에 더 많은 Key를 저장하는 만큼 트리의 높이가 더 낮아진다.
데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다.
이러한 이유로 B- Tree의 리프노드들을 LinkedList로 연결하여 순차 검색을 용이하게 하는 등 B- Tree를 인덱스에 맞게 최적화 하였다. 물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 B- Tree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.
이러한 이유로 비록 B+ Tree는 O(log2n)의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.
아래의 그림은 InnoDB에서 사용된 B+ Tree의 구조이다.
InnoDB에서의 B+ Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다.
Normalization
정규화 (Normalization)의 기본 목표는 테이블 간에 중복된 데이터를 허용하지 않는다는 것이다. 중복된 데이터를 허용하지 않음으로써 무결성(Integrity)를 유지할 수 있으며, DB의 저장 용량 역시 줄일 수 있다.
이러한 테이블을 분해하는 정규화 단계가 정의되어 있다. 여기서 테이블을 어떻게 분해되는지에 따라 정규화 단계가 달라지는데, 각각의 정규화 단계에 대해 자세히 알아보도록 하자.
제1 정규화
제1 정규화란 테이블의 컬럼이 원자값(Atomic Value, 하나의 값)을 갖도록 테이블을 분해하는 것이다. 예를 들어 아래와 같은 고객 취미 테이블이 존재한다고 하자.
위의 테이블에서 추신수와 박세리는 여러 개의 취미를 가지고 있기 때문에 제1 정규형을 만족하지 못하고 있다. 그렇기 때문에 이를 제1 정규화하여 분해할 수 있다. 제1 정규화를 진행한 테이블은 아래와 같다.
제2 정규화
제2 정규화란 제1 정규화를 진행한 테이블에 대해서 완전 함수 종속을 만족하도록 테이블을 분해하는 것이다.
Reference
