3주차 인덱스

인덱스 요약

Index는 DB의 테이블에 데이터가 많을 때, 검색 속도를 향상시켜주기위해 사용된다.

일반적으로 Index에 비유되는 예가 책의 색인 혹은 목차이다.

 

책에 색인이 없다면 '김모카'라는 단어가 몇 페이지에 있는지 찾기 위해 책의 첫 페이지부터 차례대로 찾아야 하고,

최악의 경우 마지막 페이지에 도달해서야 '길로그'라는 단어를 찾게 될 것이다.

 

하지만 색인이 있다면, 한번에 '김모카'가 있는 곳으로 찾아 갈 수 있다.

이를 해결하기 위해 책에서는 색인, DB에서는 Index를 사용한다.

 

 

Index 사용 특징

Index를 사용하면 검색 속도의 향상 효과를 볼 수 있다.

시스템 부하를 줄여, 시스템 전체 성능향상에 기여 가능 하지만 Index를 위한 추가 공간이 필요하고,

데이터가 많이 있다면 생성에 많은 시간이 소요 될 수 있다.

INSERT, UPDATE, DELETE가 자주 발생한다면 성능이 많이 하락할 수 있다.

 

 

index 생성

Index는 열 단위로 생성되는데, 하나의 열에 Index를 생성할 수 있고, 여러 열에 하나의 Index를 생성 할 수도 있다.

테이블 생성시 하나의 열에 Primary Key를 지정하면 자동으로 Clustered Index가 생성된다.

 

Clustered Index가 없는 경우

UNIQUE 제약 조건이 있는 테이블을 만들면 데이터베이스 엔진에서는 자동으로 Non-Clustered Index를 만든다.

Primary Key를 지정하는 열에 강제적으로 Non-Clustered Index를 지정 가능하다.

 

기존 테이블에 PRIMARY KEY 제약 조건을 적용하려 하거나 해당 테이블에 Clustered Index가 이미 있으면

Non-Clustered Index를 사용하여 기본 키를 적용한다.

 

제약 조건 없이 테이블 생성시에 Index를 만들 수 없으며,

Index가 자동 생성되기 위한 열의 제약 조건은 Primary Key또는 Unique 뿐이다.

 

Clustered Index

Clustered Index를 책으로 비유하자면 페이지를 알고 있어서 바로 해당 페이지를 펼치는 것과 같다.

Clustered Index는 테이블의 데이터를 지정된 컬럼에 대해 물리적으로 데이터를 재배열한다.

Index를 생성할 때는 데이터 페이지 전체를 다시 정렬

 

데이터가 테이블에 삽입되는 순서에 상관없이 Index로 생성되어 있는 컬럼을 기준으로 정렬되어 삽입된다.

데이터 삽입, 수정, 삭제시 테이블의 데이터를 정렬

Index Page를 키값과 데이터 페이지 번호로 구성하고, 검색하고자하는 데이터의 키 값으로 페이지 번호를 검색하여 데이터를 찾는다.

Clustered Index는 테이블 당 한개씩만 존재 가능하다. 

그래서 테이블에서 Index를 걸면 가장 효율적일거 같은 컬럼을 Clustered Index로 지정.

테이블에 데이터가 많이 저장된 상태에서 ALTER를 통해 Clustered Index를 추가한다면, 

많은 데이터를 정렬해야 해서 많은 리소스를 차지하게 된다. 

사용자가 많은 시간에는 함부로 Clustered Index를 추가하면 안됨

 

Clustered Index를 구성하기 위해서 행 데이터를 해당 열로 정렬한 후에, 루트 페이지를 만들게 된다. 

Clustered Index는 루트 페이지와 리프 페이지로 구성되며, 리프 페이지는 데이터 그 자체이다. 

즉, Index 자체에 데이터가 포함 Clustered Index 물리적으로 정렬되어 있어 검색 속도가 Non-Clustered Index 보다 더 빠르다. 

데이터의 입력/수정/삭제 시에도 정렬을 수행하여 입력/수정/삭제 속도는 더 느리다

 

 

Non-Clusterd Index

Non-Clustered Index를 책으로 비유하자면 목차에서 찾고자 하는 내용의 페이지를 찾고나서 해당 페이지로 이동하는것과 같다.

Non-Clustered Index는 물리적으로 데이터를 배열하지 않은 상태로 데이터 페이지가 구성된다. 

테이블의 데이터는 그대로두고 지정된 컬럼에 대해 정렬시킨 인덱스를 만들 뿐이다. 

Non-Clustered Index는 Clustered Index보다 검색 속도는 느리지만, 데이터의 입력/수정/삭제는 더 빠르다. 

Non-Clustered Index는 테이블 당 여러개 존재 가능하다. 함부로 남용하면 오히려 시스템 성능을 떨어뜨린다.

 

Non-Clustered Index는 데이터 페이지를 건드리지 않고, 별도의 장소에 인덱스 페이지를 생성한다. 

Non-Clustered Index의 인덱스 페이지는 키값(정렬하여 인덱스 페이지 구성)과 RID로 구성된다.

 

인덱스 페이지의 리프 페이지에 Index로 구성한 열을 정렬한 후 위치 포인터(RID)를 생성한다. 

Non-Clustered Index에서 인덱스 자체의 리프 페이지는 데이터가 아니라, 데이터가 위치하는 포인터(RID)다. 

RID는 '파일그룹번호-데이터페이지번호-데이터페이지오프셋'으로 구성되는 포인팅 정보. 

위처럼 리프 페이지(중간 레벨 인덱스 페이지)들을 생성하고, 

이 리프 페이지를 찾기위한 루트 페이지(루트 레벨 인덱스 페이지)를 생성한다. 

검색하고자하는 데이터의 키 값을 루트 페이지에서 비교하여 리프 페이지 번호를 찾고,

 리프 페이지에서 RID 정보로 실제 데이터의 위치로 이동한다.

 

EX : 12 검색위해 루트 페이지에서 파일 그룹번호 1에 해당하는 리프 페이지 100번으로 이동,

리프 페이지 100번에서 12는 데이터 페이지 1000번의 데이터페이지오프셋 3으로 되어 있음,

데이터 페이지 1000번으로 이동 후 3번째 컬럼으로 이동. 12, asdf5 검색 완료

 

 

 

 

B-Tree인덱스 

 

B-트리는 모든 노드가 여러키를포함하고 2개이상의자식을갖는자체균형탐색트리이다.

 

B-Tree의 다음과 같은 속성을 가지고 있습니다.

• 모든 리프 노드는동일한 수준에 있어야 한다.
• 루트를 제외한 모든 노드에는 최소 [m/2]-1개의 키와 최대 m-1개의 키가 있어야 한다.
• 루트를 제외한 모든 비 리프 노드(즉, 모든 내부 노드)에는 최소 m/2개의 자식이 있어야 한다.
• 루트 노드가 리프 노드가 아닌 경우 최소 2개의 자식 이 있어야 한다.
• n-1개의 키가 있는 비 리프 노드에는 n개의 자식이 있어야 한다.
• 노드의 모든 키 값은 오름차순 이어야 한다.

 

B-Tree에서 검색 작업

B-Tree의 검색 작업은 이진 검색 트리의 검색 작업과 유사하다. 

이진 탐색 트리에서 탐색 프로세스는 루트 노드에서 시작하고 매번 양방향 결정을 내린다

(왼쪽 하위 트리 또는 오른쪽 하위 트리로 이동). 

B-Tree에서도 검색 프로세스는 루트 노드에서 시작되지만 여기에서는 매번 n-way 결정을 내린다. 

여기서 'n'은 노드가 가진 총 자식 수입니다. B-Tree에서 탐색 연산은 O(log n) 시간 복잡도로 수행된다. 

검색 작업은 다음과 같이 수행된다.

 

1단계 - 사용자로부터 검색 요소를 읽는다.

2단계 - 검색 요소를 트리에서 루트 노드의 첫 번째 키 값과 비교한다.

3단계 - 둘 다 일치하는 경우 "주어진 노드를 찾았습니다!!!"를 표시한 뒤 함수를 종료하고

4단계 - 둘 다 일치하지 않으면 검색 요소가 해당 키 값보다 작거나 큰지 확인한다.

5단계 - 검색 요소가 더 작은 경우 왼쪽 하위 트리에서 검색 프로세스를 계속한다.

6단계 - 검색 요소가 더 크면 검색 요소를 동일한 노드의 다음 키 값과 비교하고

정확히 일치하는 항목을 찾거나 검색 요소가 마지막 키 값과 비교할 때까지 3, 4, 5, 6단계를 반복한다. 잎 노드.

7단계 - 리프 노드의 마지막 키 값도 일치하지 않으면 "요소를 찾을 수 없음"을 표시하고 기능을 종료한다.

 

 

B-트리의 삽입 작업

B-Tree에서는 리프 노드에만 새 요소를 추가해야 한다. 

즉, 새 keyValue는 항상 리프 노드에만 연결된다. 삽입 작업은 다음과 같이 수행된다.

 

1단계 - 트리가 비어 있는지 확인한다.

2단계 - 트리가 비어 있는 경우 새 키 값으로 새 노드를 만들고 트리에 루트 노드로 삽입한다.

3단계 - 트리가 비어 있지 않은 경우 이진 검색 트리 논리를 사용하여 새 키 값이 추가되는 적절한 리프 노드를 찾는다.

4단계 - 해당 리프 노드에 빈 위치가 있는 경우 노드 내 키 값의 오름차순으로 해당 리프 노드에 새 키 값을 추가한다.

5단계 - 해당 리프 노드가 이미 가득 찬 경우 중간 값을 상위 노드로 전송하여 해당 리프 노드를 분할한다.

보내는 값이 노드에 고정될 때까지 동일한 작업을 반복한다.

6단계 - 루트 노드에서 분할이 수행되면 중간 값이 트리의 새 루트 노드가 되고 트리의 높이가 1 증가한다.

 

 

B+Tree

B+Tree는 B-Tree의 개념을 조금 더 확장한 것이며 B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않지 않는다.

오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다. 

 

리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 

하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있다.)

풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형 탐색만 하면 되기 때문에 B-tree에 비해 빠르다.

B-tree의 경우에는 모든 노드를 확인해야 한다.

 

 

 

 

해시 인덱스

 

해시 인덱스 특징

해시(Hash)인덱스는 B-tree만큼 범용적이지 않지만 고유의 특성과 용도를 지닌 인덱스이다.

 

해시(Hash)인덱스는 일반적인 DBMS에서 메모리 기반의 테이블에 주로 구현되며,

디스크 대용량 테이블 용으로는 거의 사용되지 않는다는 특징을 가지고 있다. 

 

 

해시 인덱스 구조

 

해시(Hash)인덱스는 검색하고자하는 값을 주면 해시 함수를 거쳐 찾고자하는 키 값이 포함된 버켓을 찾아낸다 

 

*버킷이란, 인덱스 각 키값과 레코드의 주소값등의 정보를 두는 공간이다.

 

그렇게 버켓을 읽어 실제 레코드가 저장된 위치를 찾아내는 방법이다. 

 

 

해시 인덱스 장/단점

해시(Hash)인덱스의 장점은 해시 인덱스 구조를 보면 이해하기 쉬운 부분인데 앞에서 설명했듯이

해시 함수를 거쳐 찾고자하는 키값을 찾아내는 방식이기 때문에 

 

1. 실제 저장위치를 빠르게 알 수 있다. 

 

2. 또한 원래의 키 값을 저장하는 것이 아니라 함수 결과에 대한 값을 저장하기 때문에

컬럼 길이가 아무리 길어도 저장되는 양은 현저히 줄어든다는 장점을 가지고 있다. 

 

 

 

그에 반해 단점은

함수의 결과 값 범위가 너무 넓어져 버리면 그만큼 많은 버켓을 필요하기 때문에 공간의 낭비가 심해져 장점이 사라져버린다. 

또한, 해쉬함수를 거쳐 변형된 값을 저장하기 때문에 범위를 검색하거나, 원본값 기준으로 정렬할 수 없다. 

 

 

 

해시 인덱스 사용용도

 

변형된 값을 저장하기 때문에 범위를 검색하거나 ( >= , BETWEEN AND, < > ,LIKE),

원본값을 기준으로 정렬(ORDER BY , DESC ...)을 할 수 없는

대신 동등비교조건(==, IN, IS NULL, IS NOT NULL, <==>)일 경우에는 B-tree보다 훨씬 빠른 장점을 이용할 수 있다. 

 

 

 

 

 

 

 

https://velog.io/@gillog/SQL-Clustered-Index-Non-Clustered-Index

[SQL] Clustered Index & Non-Clustered Index

Clusterd Index와 Non-Clusterd Index 는 위 블로그 를 참조

 

https://applepick.tistory.com/155

[index] B+-Tree, Hash Table

B-Tree인덱스와 B+Tree인덱스는 위 블로그를 참조

https://najungis.tistory.com/37

해시(Hash) 인덱스 정리

해쉬 인덱스는 위 블로그를 참조