TIL - 데이터베이스와 인덱스

데이터베이스를 사용하는 이유

DB가 있기 이전에는 파일 시스템을 이용했다.

이때 각 파일 단위로 저장하였는데 데이터 종속성 문제와 중복성, 무결성 문제가 대두되었다.

 

 

 

 

 

 

 

 

 

 

데이터베이스의 성능

DB의 성능 이슈는 디스크 I/O를 어떻게 줄이느냐에서 시작된다고 한다. 데이터를 읽는데에 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 등의 성능을 통해 결정된다고 볼 수 있다.

때문에 순차 IO가 랜덤 IO보다 빠르다. 하지만 현실에서 대부분의 IO작업은 랜덤IO이다. 이런 랜덤IO를 순차IO로 바꿔서 실행할 수는 없을까? 

이런 생각에서부터 시작되는 쿼리 튜닝은 랜덤 IO 자체를 줄여주는 것이 목적이다.

 

 

 

 

 

 

 

 

 

 

인덱스

 

인덱스란 무엇인가?

인덱스는 말 그대로 책의 색인이라고 볼 수 있다. 이 비유를 그대로 가져와서 인덱슬르 살펴본다면 데이터는 책의 내용이고 이 데이터가 저장된 레코드의 주소를 페이지 번호라고 할 수 있다. 

DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져 오려면 오랜 시간이 걸린다. 그래서 칼럼 값과 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것이다.

 

DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 칼럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져서 오히려 역효과만 불러올 수 있다.

 

 

 

 

인덱스의 자료구조

 

B+Tree 또는 B-트리 알고리즘

 

 

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

 

Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

왜 index 를 생성하는데 b-tree 를 사용하는가?

데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적일 것 같은데? SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. hash table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다.

 

B-트리

B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 하며 다음과 같은 특징을 갖는다.

• 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
• 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있다.
• 노드의 키가 x개라면 자식의 수는 x+1개이다.
• 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족합니다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개입니다.)

다음은 차수가 3인 B트리이다. 파란색 부분은 각 노드의 key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 포인터이다. key들은 노드 안에서 항상 정렬된 값을 가지며, 이진검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가진다.

 

 

아래는 key를 탐색하는 과정이다.

 

 

다음은 삽입과정이다.

 Case 1. 분할이 일어나지 않는 경우

 

Case 2. 분할이 일어나는 경우

 

 

 

다음은 삭제과정이다.

 

Case 1. 삭제할 key k가 리프에 있는 경우

 

 

 

Case 2. 삭제할 key k가 내부 노드에 있고, 노드나 자식에 키가 최소 키수보다 많을 경우

 

 

 

Case 3. 삭제할 key k가 내부 노드에 있고, 노드에 key 개수가 최소key 개수만큼, 노드의 자식 key 개수도 모두 최소 key 개수인 경우

B+트리

 

실제 대부분의 DB 인덱싱은 B+트리로 이루어져 있다. 

 

B+트리 달라진 점은 다음과 같다.

1. 모든 key, data가 리프노드에 모여있다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가진다.
2. 모든 리프노드가 연결리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
3. 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같다. 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어난다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용하였다.

key 삽입과정

 

삽입 후 부모 key를 삽입된 key로 갱신하고, data를 넣어준다.

 

 

Case 3. 분할이 일어나는 삽입과정

 

 

 

key 삭제과정

Case 1. 삭제할 key k가 index에 없고, 리프노드의 가장 처음 key가 k가 아닌경우

 

 Case 2. 삭제할 key k가 리프노드의 가장 처음 key인 경우

 

 

 

다음시간에 공부할 것.

 

클러스터링 인덱스

 

 

 

 

 

 

 

 

 

 

출처

 

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4

GitHub - JaeYeopHan/Interview_Question_for_Beginner: Technical-Interview guidelines written for those who started studying progr

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

[자료구조] 그림으로 알아보는 B-Tree

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

[자료구조] 그림으로 알아보는 B+Tree