search

topgaren / DevStudy

0 stars 0 forks source link

Database #3

Open topgaren opened 4 years ago

topgaren commented 4 years ago

Database Study

topgaren commented 4 years ago

관계형 데이터베이스(RDB; Relational Database)

topgaren commented 4 years ago

인덱스(Index)

1. 인덱스 개요

인덱스(Index)는 주로 책의 제일 끝에 존재하는 찾아보기(또는 색인)로 비유된다. 책의 내용을 데이터베이스에 저장된 레코드라고 하면 찾아보기는 인덱스, 찾아보기에 있는 페이지 번호는 레코드의 주소에 해당한다고 볼 수 있다. 또한 찾아보기의 키워드는 인덱스의 키에 해당한다. 책의 찾아보기도 그 내용이 많아지면 원하는 키워드를 찾아내는데 시간이 걸리게 된다. 그래서 "ㄱ", "ㄴ", "ㄷ"... 또는 "A", "B", "C"... 와 같이 키워드가 정렬되어 있는데, 데이터베이스의 인덱스 또한 인덱스 키를 정렬하여 관리한다.

인덱스를 사용하면 정렬된 인덱스 키를 기반으로 매우 빠른 데이터 조회가 가능하다. 그러나 인덱스 키를 항상 정렬 상태로 유지시켜야 한다는 점 때문에 데이터 조작(Insert, Delete, Update)에 대한 성능은 떨어진다. 따라서 인덱스를 생성하는 것은 데이터의 조작과 조회의 정도에 따라 결정되어야 한다. WHERE 조건절에 사용되는 컬럼을 모두 인덱스로 생성하면 데이터의 조작 성능이 떨어지고 인덱스 관리에 따른 오버헤드로 오히려 성능에서 역효과가 발생할 수 있다.

2. 인덱스의 동작 원리(B-Tree, B+-Tree)

인덱스 키를 관리하는 알고리즘에는 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다.

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

Hash 인덱스 : 컬럼 값으로 해시(Hash) 값을 계산해서 인덱싱 하는 알고리즘으로 매우 빠른 검색을 지원한다. 그러나 값을 변형하기 때문에 전방(Prefix) 일치와 같이 값의 일부분을 이용하는 검색은 해당 알고리즘으로는 사용할 수 없다. Hash 인덱스는 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

2-1. B-Tree 인덱스

데이터베이스의 인덱싱 알고리즘 가운데 가장 범용적으로 사용되는 알고리즘이다. 참고로 B-Tree의 "B"는 "Binary(이진)"가 아니라 "Balanced"를 의미한다. 인덱스 정보도 HDD와 같은 보조 기억 장치에 저장되기 때문에 인덱스를 참조하는 과정은 반드시 디스크 I/O가 발생한다. Tree의 깊이가 깊을수록 더 많은 노드를 참조하게 되고 결국 디스크 I/O의 횟수가 증가하게 된다. Balanced-Tree를 통해 최소한의 깊이로 Tree를 구성하면 최소한의 디스크 I/O로 인덱스를 관리할 수 있다. 또한 디스크 I/O의 효율을 최대한 높이기 위해 B-Tree 노드의 크기를 디스크 I/O의 기본 단위에 맞게 설정한다.

B-Tree의 노드는 다음과 같이 3 종류로 구분할 수 있다.

image

이미지 출처 : 위키백과 "B-tree"

2-2. B+-Tree 인덱스

B+-Tree 인덱스의 예 image

이미지 출처 : 위키백과 "B+ 트리"

2-3. B-Tree와 B+-Tree 인덱스의 차이

B-Tree 인덱스 키와 이에 해당하는 레코드의 주소 값 등의 정보를 인덱스 키를 포함하는 노드에 저장한다. 즉 각 노드에 데이터가 저장된다. 그렇기 때문에 리프 노드에 도달하기 전에 값을 찾아낼 수 있고, 탐색 시간이 탐색 키 수의 로그에 비례한다.

B+-Tree B+-Tree는 레코드의 주소 값 정보를 모두 리프 노드에 저장하고, 브랜치 노드에는 인덱스 키와 자식 노드의 포인터만 저장한다. 즉 인덱스 노드와 실제 데이터의 정보가 저장된 리프 노드가 분리되어 존재한다. 리프 노드들은 서로 Linked List 형태로 연결되어 있어 임의 접근과 순차 접근 모두 성능이 우수하다. B+-Tree는 기존의 B-Tree에 리프 노드 간에 Linked List 구조가 추가된 것이라고 할 수 있다.

3. 효과적으로 인덱스를 사용하는 방법

Reference https://d2.naver.com/helloworld/1155 https://12bme.tistory.com/138 https://asfirstalways.tistory.com/339

topgaren commented 4 years ago

정규화(Normalization)

1. 제 1정규화(1NF)

2. 제 2정규화(2NF)

3. 제 3정규화(3NF)

4. BCNF

topgaren commented 4 years ago

트랜잭션(Transaction)

topgaren commented 4 years ago

파티셔닝(Partitioning) & 샤딩(Sharding)