'Computer Science/데이터베이스'에 해당되는 글 7건

1. ISAM 트리구조

정적 트리구조

삽입 / 삭제를 하여도 트리의 구조가 변화하지 않는 것이 특징이다. 만일 페이지에 더 이상 데이터를 추가할 수 없다면 오버플로우 페이지를 생성하여 마지막 리프노드에 체인으로 연결하여 추가한다.

오버플로우 페이지

위의 그림 왼쪽 트리 구조에서 7을 삽입하는 연산이 수행한다고 가정하자. 루트에서 시작해서 리프 노드에 도달하면 7이 들어갈 노드가 (6*, 9*)로 채워져 들어갈 공간이 없다. 이때 ISAM 트리 구조는 트리의 구조를 변형시키지 않고 아래에 7이 들어갈 수 있는 공간을 만든 후 다음 7을 삽입한다. 이 때 새로 만들어진 이 공간을 오버플로 페이지라고 한다. 

오버플로 페이지를 생성함에 따라서 얻을 수 있는 이득은 오버플로가 발생하는 경우 삽입 / 삭제 연산이 B+ 트리보다는 빠르다는 점이다. 아래에 설명할 B+트리는 동적 트리구조로 만약 위의 그림과 같은 상황이 발생하면 트리 구조를 변형을 하여 삽입을 시도하기 때문이다. 또한 Lock을 거는 경우 트리의 내용물에는 변화가 없기 때문에 리프 노드에만 Lock을 걸면 된다. 하지만 오버플로 페이지가 많이 발생할수록 위 그림에서 눈치챘을지도 모르지만 데이터를 물리적으로 정렬하지 않기 때문에 데이터를 탐색하는 속도는 늦어어진다는 단점이 있다.

2. B+ 트리구조

동적 트리구조

ISAM 트리와 달리 삽입 / 삭제시에 트리구조가 변화가 발생하는  특징이 있다. 또한 Root 노드를 제외한 나머지 노드들은 데이터를 반드시 절반 이상 점유해야 하는 필수 조건이 있다. 

삽입 연산

위의 트리에서 8을 삽입한다고 가정하자. 8은 L2에 삽입되어야 하지만 현재 노드가 꽉 차있어서 삽입을 할 수 없다. B+ 트리는 오버플로 페이지를 생성하지 않고 L2를 쪼개서 새로운 노드를 만드는 방법을 사용한다. 8을 포함한 L2의 구성 요소 (5,6,7,8,9) 중 중간 값인 7은 상위 단계 노드로 Copy up 되고 트리구조의 특징상 기존의 L2(5,6,7,8,9)는 L2(5,6), L3(7,8,9)로 갈라지게 되어 아래 그림과 같이 된다.

따라서 삽입 연산 중 리프 노드에서 오버플로가 발생하면 B+트리는 해당 노드의 중간 값이 상위 노드로 Copy up 하는 과정이 발생한다. 만일 Copy-up 과정에서 상위 레벨 노드마다 오버플로가 발생한다면 어떻게 트리구조가 변화할까?

위의 그림과 같은 트리에서 15가 삽입된다고 가정하자. 15가 삽입될 노드는 L4인데 L4가 가득 차있으니까 아까 위에서 Copy up을 시도한다. L4(13,14,15,16,18) 중에서 중간 값인 15가 상위 단계 노드로 Copy up이 되려는 순간 상위 노드가 꽉 차있다. 따라서 상위 노드도 분열이 되어야 하는데 이 과정에서 분열된 상위 노드들을 연결할 새로운 루트 노드가 필요하다.  상위 노드의 값 (5, 7, 13, 15, 20) 중 중간 값인 13이 한 단계 상승한 Push up 과정이 발생하고 나머지 (5,7) (15,20)이 다음 노드로 연결되는 아래 그림과 같은 트리구조로 변화한다.

기존 트리의 높이는 1이였지만 삽입의 결과로 높이가 2로 변화하였다. B+트리는 이처럼 트리의 구조를 유지하기 위해서 Copy up / Push up 알고리즘을 사용하고 경우에 따라서 트리의 높이가 변화할 수도 있다.

삭제 연산

삭제 연산에서 가장 중요한 키워드는 루트를 제외한 각 노드는 점유율을 항상 50%이상 유지한다는 점이다. 만약 50프로가 안된다면 인접한 노드에서 빌려온다. 그런데 빌려 오니까 인접 노드도 점유율 50%를 만족하지 못한다면 인접 노드와 병합하는 방법으로 점유율 50%를 유지한다.

위 그림(아까 삽입한 결과)에서 24*를 삭제하는 연산을 수행한다고 하자. L6은 이제 데이터가 (21*)만 존재하게 되어 데이터의 점유율이 50프로 미만이 되어버렸다. 따라서 인접 노드인 L5에서 데이터를 (18*)를 빌려온다. L5도 (15*, 16*)을 가지고 있고 L6도 (18*, 21*)로 50프로를 유지할 수 있으므로 L6의 최솟값 18*을 상위 노드에 20*으로 Copy up 하는 것으로 마무리한다. 결과는 아래의 그림과 같다.

이번에는 L1의 1을 삭제한다고 가정하자. 1이 삭제된 L1은 (2*)만 남아 50프로를 유지할 수 없고 인접 노드 L2의 5*를 빌려서 채울려고 하지만 그렇게 진행하면 L2도 (6*)만 남아 점유율 50프로를 만족하지 못한다. 따라서 L1과 L2는 합병이 된다.

합병을 하고 상위 노드 I1의 5*를 삭제하니 I1도 50프로를 만족하지 못한다. 인접 노드 L2에서 데이터를 하나 빌릴려고 하니 연산 결과 L2도 50%를 만족하지 못한다. 따라서 합병을 해야하는 상황이 발생한다. 

합병을 할 때 상위 노드의 값은 한 단계 내려와 Pull down되어 I1, I2와 함께 합쳐진다.  그 외 여기서 다루진 못했지만 만약 I1이 데이터가 4개 있고 삭제당한 I2의 데이터가 1개 있다면 합병하게 되면 5개가 돼버려서 오버플로가 발생하는 경우가 있다. 이 경우에는 재분산(Re-distribution)을 사용하여 2개 / 3개로 다시 나누어 주는 과정이 있다. 기존의 트리의 높이는 2였지만 모든 삭제 연산을 수행한 후에 보면 높이 1의 트리로 변화하였다. 

트리 구조를 유지하면서 이득 / 손해

우선 이득은 데이터 탐색 속도가 ISAM보다 빠르다. 오버플로 페이지가 발생하지 않고 데이터가 삽입되면 그 데이터를 물리적으로 정렬하기 때문이다. 대신 삭제나 삽입의 경우 트리 구조를 유지해야 하는 면에서 ISAM에 비하면 복잡한 과정이 있기 때문에 비용이 좀 더 드는 손해는 있다. 하지만 인덱스를 사용하는 이유는 탐색 속도의 향상이므로 대부분 상용 DBMS에서는 B+ 트리를 사용하여 인덱스를 만든다.

1. Buffer Management

Buffer Management의 역할

사용자가 어떤 쿼리문을 요청하면 DB에서 해당 내용을 메인 메모리의 버퍼 풀에 저장하여 사용한다. 요청한 페이지가 버퍼 풀에 없다면 한 프레임을 대체하여 사용하며 대체되는 프레임이 변경(dirty)되었다면 해당 내용을 디스크 상에도 반영을 하여 준다. 만약 순차적인 스캔 등 다음에 읽을 페이지가 예상이 가능하다면 미리 여러 개의 페이지를 메모리 상에 올려 주는 것이 효과적이다. 

Buffer Replacement Policy

LRU, MRU, Clock 등등 다양한 교체 알고리즘으로 정책을 세우되 접근 패턴을 고려하여 선택을 해야한다. 만약 버퍼 프레임보다 페이지의 수가 많다면 Sequential flooding이 발생한다. LRU를 사용하면 I/O하는 시간이 많이 소비되어 이 경우에는 MRU가 비교적 효과적인 알고리즘이 된다. 

2. InnoDB record format

Variable Length

한 필드의 타입이 int(4)라면 int형 데이터를 무조건 4개를 넣어라는 것이 아니라 4개 이하의 데이터를 넣을 수 있으며 not null 조건이 없다면 null도 허용된다. 이처럼 데이터 필드의 크기가 변화가능한(variable) InnoDB의 데이터 필드를 저장할 때 각각의 필드의 시작지점을 저장하는 Field Start offset을 함께 저장한다.

Record format

우선 가장 앞의 Field start offset은 각각의 칼럼의 시작 위치를 저장하는 곳이며 Extra Byte 구간을 기준으로 좌우 대칭된 모습으로 저장한다. 대게 1Byte를 사용하며 가장 첫 비트는 null여부를 판단하는 비트로 사용한다. 예를 들어 F3가 1000 0001이라면 해당 데이터 필드는 null이다. 따라서 표현가능한 크기는 127이하를 표기 가능하며 만약 127이상의 데이터 필드가 있다면 1 바이트를 추가적으로 사용하여 표기가능하다. 두 바이트를 사용하는 경우에는 첫 비트는 null여부, 두 번째 비트는 같은 페이지에 데이터가 있는지 여부를 표기한다. 왜나햐면 크기를 나타내는 비트의 수가 14개이므로 최대 16,383byte를 표현 가능하므로 같은 필드의 데이터가 다른 페이지 상에 존재할 가능성이 있기 때문이다.

Extra Byte는 Field start offset이 1바이트인지 2바이트인지, 다음 레코드의 포인터값 등등을 저장하는 필드이다. InnoDB에서는 6바이트를 사용하여 정보를 표기한다.

System Column에는 해당 rowID(S1), 트렌젝션ID(S2), Rollback pointer(S3)를 담고 있으며 해당 크기는 각각 6바이트,  6바이트, 7바이트이다. Rollback pointer의 경우 트렌젝션 수행 중에 만일 Rollback을 하게 되면 해당데이터가 원상 복구되어야하는데 변경 전의 데이터를 가지고 있는 필드를 가리키는 포인터로 사용한다.

1. InnoDB

Clustered index

MySQL은 InnoDB에서 작동하는 SQL이다. 그리고 이 InnoDB는 테이블의 기본 키(PK)를 인덱스로 하여 사용하며 동기화 되어 저장한다. 다시 말해 데이터가 변경, 삭제, 삽입이 발생하면 기본 키에 대하여 데이터 레코드를 정렬을 한다. 만약 기본키가 없는 테이블은 not null인 Unique Key를 사용하고 그것마저도 없으면 내부적으로 숨겨진 Row ID를 사용하여 사용하며 새로운 열에 대하여는 단계적으로 증가한 ID값을 넣어 사용한다. 

Secondary index 

InnoDB는 Clustered index를 제외한 나머지 인덱스를 보조 인덱스로 사용한다. 이론적으로 non-clustered index를 사용하면 해당 레코드의 RID(Row ID)로 데이터 레코드에 접근하는데 InnoDB에서는 RID 대신 기본 키 로 대체하여 사용한다. 따라서 기본 키의 크기가 매우 긴 경우에는 보조 인덱스의 크기가 비대해질수도 있으므로 기본키의 크기를 작게 사용하는 것이 좋다.

2. Index Query

index 생성

1. 기본 키 또는 Unique key 선언된 테이블 생성 시 자동으로 생성

2. 기본 키가 없는 테이블에 기본 키를 지정하는 경우

3. 직접 index 생성

Index Hint

DB가 보통 최적의 인덱스를 선택하는 경우도 있지만 인덱스의 선택이 옳지 못한 경우에는 사용자가 직접 인덱스 힌트를 줘서 사용을 강제로 하거나 사용을 못하게 막을 수 있다. 

use : 인덱스를 써 볼 것을 권유... (최적화를 고려하므로 강제성이 없다.)

force : 강제로 인덱스 사용. (Table Scan이 더 효율적인데도 강제적으로 사용한다) 

ignore : 해당 인덱스를 사용을 금지한다.

Index List

해당 테이블에 어떤 인덱스가 있는지 확인할 수 있는 쿼리

1. Workload

인덱스는 양날의 검이다.

탐색 속도를 향상시켜주는 인덱스의 장점이 있지만 잘못된 인덱스의 선택은 오히려 작업량을 늘릴 수 있기 때문에 인덱스의 선택은 상황을 판단하여 신중히 행하여야 한다. 또한 DBMS마다 지원하는 index방식이 다르기 때문에 각각의 DBMS에서 사용하는 방식에 대한 이해가 필수적이다. 

예를 들면 MySQL의 경우 테이블의 기본 키(Primary key)로 자동으로 클러스터화된 인덱스를 생성한다. 

따라서 언클러스터화된 인덱스는 MySQL DBMS에서는 사용이 불가능하다. 

또한 인덱스는 테이블의 갱신 속도를 늦추기 때문에 아무렇게 인덱스를 짜면 안된다. 왜냐하면 인덱스가 정의된 데이터 테이블들은 인덱스에 따라 물리적 또는 논리적으로 정렬을 하기 때문에 삽입, 삭제, 변경이 발생하면 다시 재정렬을 하여야하므로 잦은 입출력이 있는 은행이나 게시물 등에 아무렇게 인덱스를 사용하면 성능을 저하시킬 수 있다. 

2. Clusetered Index

탐색키가 하나인 경우

Clustered index는 테이블에 단 하나만 생성할 수 있으므로 어떤 탐색키를 사용할 지 선택을 신중하게 하여야 한다. 각각의 쿼리와 조건에 따라서 index를 사용한 탐색을 할지 테이블 전체를 스캔할지 선택하여한다.

위의 쿼리에서 E.age를 index로 사용할지 선택하라면 Emp 테이블의 40세 이상의 비율이 어느 정도 인지 확인이 필요하다. 40세 이상의 인원이 적다면 인덱스를 통한 탐색을 매우 유용할수 있다. 하지만 40세 이상의 비율이 대다수이라면 굳이 인덱스를 통한 탐색이 아니라 테이블 전체를 스캔하는 것이 더욱 효율적이다. 왜냐하면 클러스터화된 인덱스의 경우는 모든 데이터 레코드들이 물리적으로 탐색키에 맞게 정렬이 되어 있다. 

위의 쿼리는 각각의 부서별로 사원의 나이가 10세 초과인 사람의 수를 구하는 쿼리다. dno와 age중 어떤 것을 index로 고른다고 한다면 10세 초과의 사원의 수가 전체 데이터에 어느 정도를 차지하는지 알아야할 필요가 있다. 만일 10세이상의 사원이 첫 번째 사례처럼 대다수라면 인덱스로 사용하는 것은 부적절하다. 오히려 dno를 인덱스로 사용한다면 더욱 효율성이 있을 것이다. 데이터들은 dno에 따라 정렬이 되어 있으므로 인덱스를 탐색한 후에 조건에 맞는 것만 세면 되기 때문이다.

두 개 이상의 탐색키 활용

직원의 나이를 나타나는 age와 봉급을 나타나는 sal을 탐색 키로 사용하는 클러스터화된 인덱스가 있다고 하자. 어떤 것을 우선적으로 정렬하는 가에 따라 <age, sal> , <sal, age> 둘 중에 하나를 사용할 수 있다.

1. 만일 age = 30 이고 sal = 4000인 사람을 찾아라 

 <age, sal> 이나 <sal, age> 둘 다 효과적이다. 만일 age 를 단독으로 인덱스로 사용한다면 age가 30인 사람은 금방 찾지만 sal이 4000인 사람은  해당 age 전체를 탐색하여야 한다. 하지만 인덱스로 <age, sal>을 찾는 경우는 모든 데이터 레코드들이 age로 정렬된 후 sal로 정렬하기 때문에 4000인 사람을 쉽게 찾을 수 있다.

2.  age = 30 이고 3000<sal<5000인 직원을 찾아라

<age, sal>이 <sal, age>보다 더욱 효과적이다. age=30를 찾은 다음에 그 후 sal로 정렬된 데이터 레코드를 수평으로 이동하면서 범위 탐색을 할 수 있어서 <age, sal> 가 더 효율적이다.

따라서 <age, sal>, <sal, age>중 선택하는 방법은 둘 중에 어떤 것이 작은 범주에 들어가는냐는 것을 생각을 하고 선택하는 것이 옳다. 

3. Unclustered Index

index-only plan

Unclustered Index의 경우 데이터 엔트리상에 탐색 키로 논리적으로 정렬이 되어있고 데이터 레코드들이 물리적으로 정렬하지 않는다. 따라서 데이터 엔트리에서 데이터 레코드로 직접 탐색하기 전에 데이터 엔트리내에서 찾아서 식별하는 것이 답을 찾아낼 수 있는 적절한 인덱스의 선택이 필요하다.  나머지 인덱스의 사용에 고려할 사항은 위의 클러스터화된 인덱스와 유사하여 생략한다.

1. 인덱스(index)

사전에서 APPLE의 뜻을 찾고자 할 때 두 가지의 방법을 사용할 수 있다.

첫번째는 처음부터 하나하나씩 단어를 훑으면서 찾는 방법

두번째는 사전 옆에 붙어있는 A -> P ->.. 순서로 찾는 방법

둘 중에 탐색하는 속도는 두 번쨰의 경우가 더욱 빠르게 탐색이 가능하다.

이처럼 인덱스는 데이터 베이스에서 데이터 탐색 속도를 향상시켜주는 자료 구조이다.

만일 Search Key가 Primary Key를 포함한다면 Primary Index라고 하며, Unique Key를 포함한다면 

Unique Index라고 한다.

2. Clustered vs Unclustered Index

Clustered index와 Unclustered Index의 큰 차이점은 Sorting의 여부이다.

Clustered index는 Date Record가 Key 값을 기반으로 정렬하여 정렬하여 저장한다.

따라서 여러 개가 있으면 데이터 정렬의 순서가 꼬이므로 단 하나만 생성할 수 있다.

또한 정렬이 되어있는 특징 덕분에 전반적으로 불러오기 속도를 엄청나게 향상시키는 효과가 있다.

반면 Unclustered index의 경우 Date Record의 정렬을 하지 않고 저장한다. 

그리고 index 테이블에는 논리적으로 정렬하고 데이터가 있는 페이지 번호와 위치를 표기한다.

따라서 index 테이블은 논리적 정렬을 위해 여러 개가 존재해도 무관하고 덕분에 파일의 크기도 증가한다.

3. Hash-Based Index

해시 인덱스는 검색하고자하는 값을 해시함수에 입력한 후 그 결과와 Bucket의 내용과 비교하여

해당 데이터 레코드의 위치를 찾을 수 있는 인덱스 기법이다. 이 기법의 장점은 Equality 연산에는 좋은 성능을 보인다는 점, 그리고 해시 함수를 특징상 입력 값에 비해 출력 값의 크기는 줄여 Bucket에 저장한다는 점이다. 반면에 단점은 범위를 탐색하는 경우에 매우 비효율적인 성능을 보여준다는 점이다. 

4. B+ Tree Index

B+ Trees는 관계형 데이터 베이스에서 가장 일반적으로 사용되는 인덱스이다.

자료구조때 이진 트리처럼 가운데 키 값과 작거나 같으면 왼쪽 크면 오른쪽으로 트리를 구성한다.

다만 다른 점은 Leaf 노드 간 이동이 가능하다는 점이다. 

Leaf 단계에서 데이터 엔트리들이 포함되어 있기 때문에 B+ Tree의 성능은 트리의 깊이에 의하여 좌우된다.

범위 탐색의 경우에는 Root에서 시작하여 최소 경계값을 찾고 다음 리프 노드로 넘어가는 방식으로 연산을 수행한다. 삽입의 경우에는 필요에 따라 부모 노드가 조정될 수 있다. 마지막 리프 노드가 꽉 차있다면 다시 쪼개서 트리구조를 유지하기 떄문이다.

관계대수(Relation Algebra)

2. 추가 연산자 : 기본 연산자들의 조합으로도 만들수 있지만 알고 있으면 편하자나!(내 맘은 불편..)

  1) Join() 

    (1) Condition Join(=Theta-join) : Cross-product를 수행한 후 Selection을 한 결과

    (2) Equi-Join : 조인 대상이 되는 두 테이블에서 공통적으로 존재하는. 컬럼의 일치되는 행을 연결하여 

                              결과를 생성하는 조인 방법 

                              (공통적인 필드는 하나만 표기한다)

    (3) Natural Join : 모든 공통적인 필드에 대한 Equi-Join 

  2) Division( / ) 

    A에 존재하는 <x, y> 튜플에 대하여 B의 모든 튜플 <y>를 포함하는 튜플 <x>의 집합 

 3) Renamimg operator() : 연산 결과를 임시 테이블에 저장하거나 도메인을 변경하기 위한 연산자

    A - B 의 결과로 반환된 Relation명을 Temp라 하고 

     Temp의 첫번째 도메인은 userID 세번째 도메인은 result라고 변경한다.

관계대수(Relation Algebra)

1. 기본 연산자

  1) Selection() : Relation에서 조건에 만족하고 중복 없는^[각주:1] 튜플(tuple)들의 Relation을 반환 

     ex)  userTable에서  이름이 ssooni인 사람의 모든 정보를 구하기

           관계대수 > 

           SQL query >  Select * from userTable where name = 'ssooni' 

  2) Projection() : Relation에서 원하는 속성(attribute)에 해당하는 중복 없는 튜플(tuple)들로 

                            구성된 Relation을 반환

     ex)  userTable에서 이름이 ssooni인 사람의 전화번호를 구하기

           관계대수 > 

           SQL query > Selete phoneNum from userTable where name='ssooni'

  3) Cross-product() :  두 개의 Relation들을 조합하는 연산자 

  4) Set-difference( - ) : 차집합 연산,  연산하고자 하는 Relation들의 각각 대응하는 필드(field)들은 동일한 타입

  5) Union() : 합집합 연산,  연산하고자 하는 Relation들의 각각 대응하는 필드(field)들은 동일한 타입