Anomaly, Index

Anomaly

 

 

정규화를 해야하는 이유는 잘못된 테이블 설계로 인해 Anomaly(이상 현상)이 나타나기 때문이다.

예를 들어서 {Student ID, Course ID, Department, Course ID, Grade} 가 있다고 해보자.

 

① 삽입 이상(Insertion Anomaly)

예를 들어서 기본키가 {Student ID, Course ID} 두개일 경우, Course를 수강하지 않은 학생은 Course ID가 없는 현상이 발생하므로 Course ID를 Null 로 지정해야 한다.

그러나 기본키는 Null이 될 수 없으므로 테이블에 추가할 수 없다. ('미수강' 과 같은 Course ID로 대체 가능하긴 함)

 

즉, 불필요한 데이터를 추가해야만 삽입할 수 있는 상황을 삽입 이상이라고 한다.

 

② 갱신 이상(Update Anomaly)

어떤 학생의 전공이 "전자"에서 "기계"로 바뀌는 경우, 모든 Department를 "기계"로 바꿔야 한다.

그러나 일부를 깜빡하고 바꾸지 못할 경우 제대로 파악하기 어렵다.

 

즉, 일부만 변경하여 데이터가 불일치 하는 모순의 문제를 갱신 이상이라고 한다.

 

③ 삭제 이상(Deletion Anomaly)

만약 어떤 학생이 수강을 철회할 경우, Student ID, Department 와 같은 학생에 대한 정보도 함께 삭제되는 경우가 존재한다.

 

즉, 튜플 삭제로 인해 꼭 필요한 데이터까지 함께 삭제되는 문제를 삭제 이상이라고 한다.

 

 

INDEX

 

INDEX(인덱스)란?

 

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

테이블의 칼럼을 색인화한다.

데이터베이스 안의 레코드를 처음부터 모두 스캔하지 않고 B+ Tree로 구성된 구조에서 Index 파일 검색으로 속도를 향상시키는 기술이다.

 

B+ Tree는 무엇인가요?

 

참고 : B+ 트리 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

B+ 트리(Quaternary Tree라고도 알려져 있음)는 컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종이다.

이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성된다.

B트리와 대조적으로 B+트리는, 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다.

오직 키들만이 내부 블록에 저장된다.

 

 

※ 파일 구성

테이블 생성 시, 3가지 파일이 생성된다.

• FRM : 테이블 구조 저장 파일
• MYD : 실제 데이터 파일
• MYI : Index 정보 파일 (Index 사용 시 생성됨)

 

사용자가 쿼리를 통해 Index를 사용하는 칼럼을 검색하게 되면 MYI 파일의 내용을 활용한다.

 

※ 단점

① Index 생성 시, .mdb 파일 크기가 증가한다.

② 한 페이지를 동시에 수정할 수 있는 병행성이 줄어든다.

③ 인덱스 된 Field에서 Data를 업데이트하거나 Record를 추가 또는 삭제시 성능이 떨어진다.

④ 데이터 변경 작업이 자주 일어나는 경우 => Index를 재작성해야 하므로 성능에 영향을 미친다.

 

Index를 사용하면 좋은 경우는 어떤 경우인가?

 

• Where 절에서 자주 사용되는 Column
• 외래키가 사용되는 Column
• Join에 자주 사용되는 Column

 

Index 사용을 피해야 하는 경우는 어떤 경우인가? 

 

• Data 중복도가 높은 Column
• DML이 자주 일어나는 Column

 

※ DML이 일어난 경우

 

① INSERT

기존 Block에 여유가 없을 때, 새로운 Data가 입력된다.

이때 새로운 Block을 할당 받은 후에 Key를 옮기는 작업을 수행한다.

Index split 작업 동안, 해당 Block의 Key 값에 대해서 DML이 블로킹 된다. (대기 이벤트 발생)

 

② DELETE

• Table : data가 삭제되는 경우, data가 지워지고 다른 data가 그 공간을 사용 가능하다.  
• Index : data가 삭제되는 경우, data가 지워지지 않고, 사용 안 됨 표시만 한다.

 

③ UPDATE

• Table 에서 update가 발생하면, Index는 업데이트 할 수 없다.
• Index 에서는 delete가 발생한 후, 새로운 작업의 insert 작업 / 2배의 작업이 소요되어 힘들다.

 

※ Index 자료구조

 

DBMS 는 인덱스를 어떻게 관리하는지 알아보도록 한다.

 

① B+ Tree 인덱스 알고리즘

일반적으로 사용되는 인덱스 알고리즘은 B+ Tree 알고리즘이다.

B+ Tree 인덱스는 칼럼의 값을 변형하지 않고(사실 값의 앞부분만 잘라서 관리), 원래의 값을 이용해 인덱싱하는 알고리즘이다.

 

② Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다.

하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다.

주로 메모리 기반의 데이터베이스에서 많이 사용한다.

 

index 를 생성하는데 B Tree 를 사용하는 이유?

 

데이터에 접근하는 시간복잡도 O(1) 인 hash table 이 더 효율적이지만,

SELECT 질의의 조건에는 부등호(< >) 연산도 포함이 된다.

즉, hash table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다.

동등 연산(=)에 특화된 hashtable 은 데이터베이스의 자료구조로 적합하지 않다.

 

 

※ Index 의 성능과 고려해야할 사항

 

SELECT 쿼리의 성능을 월등히 향상시키는 INDEX 항상 좋은 것일까?

쿼리문의 성능을 향상시킨다는데, 모든 컬럼에 INDEX 를 생성해두면 빨라지지 않을까? 

결론부터 말하자면 그렇지 않다. 

우선, 첫번째 이유는 INDEX 를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생한다.

INSERT 의 경우 INDEX 에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따른다.

DELETE 의 경우 INDEX 에 존재하는 값은 삭제하지 않고 사용 안한다는 표시로 남게 된다.

즉 row 의 수는 그대로인 것이다. 이 작업이 반복되면 어떻게 될까?

 

실제 데이터는 10 만건인데 데이터가 100 만건 있는 결과를 낳을 수도 있는 것이다.

이렇게 되면 인덱스는 더 이상 제 역할을 못하게 되는 것이다.

UPDATE 의 경우는 INSERT 의 경우, DELETE 의 경우의 문제점을 동시에 수반한다.

이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 때문이다.

즉 변경 전 데이터는 삭제되지 않고 insert 로 인한 split 도 발생하게 된다.

 

하지만 더 중요한 것은 컬럼을 이루고 있는 데이터의 형식에 따라서 인덱스의 성능이 악영향을 미칠 수 있다는 것이다. 즉, 데이터의 형식에 따라 인덱스를 만들면 효율적이고 만들면 비효율적은 데이터의 형식이 존재한다는 것이다.

어떤 경우에 그럴까?

 

이름, 나이, 성별 세 가지의 필드를 갖고 있는 테이블을 생각해보자.

이름은 온갖 경우의 수가 존재할 것이며 나이는 INT 타입을 갖을 것이고, 성별은 남, 녀 두 가지 경우에 대해서만 데이터가 존재할 것임을 쉽게 예측할 수 있다.

이 경우 어떤 컬럼에 대해서 인덱스를 생성하는 것이 효율적일까?

결론부터 말하자면 이름에 대해서만 인덱스를 생성하면 효율적이다.

 

왜 성별이나 나이는 인덱스를 생성하면 비효율적일까?

10000 레코드에 해당하는 테이블에 대해서 2000 단위로 성별에 인덱스를 생성했다고 가정하자.

값의 range 가 적은 성별은 인덱스를 읽고 다시 한 번 디스크 I/O 가 발생하기 때문에 그 만큼 비효율적인 것이다.

 

 

참고 : gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖 (github.com)

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖