# DDIA 3장. 저장소와 검색

* 데이터베이스는 기본적으로 두 가지 작업을 수행한다:
  * 데이터를 받으면 데이터를 저장한다.
  * 나중에 그 데이터를 요청하면 데이터를 제공한다.

## 데이터베이스를 강력하게 만드는 데이터 구조

* kvp로 구성되어 `set`과 `get`으로 데이터를 저장, 요청할 수 있는 데이터베이스를 생각해보자.
* 레코드가 방대하면 `get` 성능이 $O(n)$으로 좋지 않다. 이를 해결하기 위해 색인(Index)을 사용한다.

### 해시 색인

* kvp 데이터를 색인하기 위해 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 만들 수 있다.
* 램에 모든 키를 저장하면 고성능의 읽기, 쓰기가 가능 하지만 결국 디스크 공간이 부족해지는 문제가 있다.
* 특정 크기의 세그먼트로 데이터를 나누면 된다:
  * 데이터가 특정 크기에 도달하면 기존 세그먼트를 닫고, 새로운 세그먼트에 쓰기를 수행하는 컴팩션을 진행한다.
  * 중복된 키를 버리고 각 키의 최신 값을 유지하기 때문에 공간을 줄일 수 있다.
* 하지만 해시 테이블 색인은 제한 사항이 있다:
  * 해시 테이블을 메모리에 저장해야 하므로 키가 너무 많으면 입출력이 많이 필요하다.
  * 디스크가 가득차면 확장하는 비용이 든다. 또한 해시 충돌 해소를 위해 성가신 로직도 필요하다.
  * 해시 테이블은 범위 질의에 효율적이지 않다. 범위 질의를 수행하기 위해선 모든 개별 키를 조회해야 한다.

### SS테이블과 LSM 트리

* SS테이블(Sorted String Table)은 일련의 kvp를 키로 정렬한 테이블이다.
* 키가 정렬되어 있으면 세그먼트 병합을 효율적으로 할 수 있다.
* 주변 키의 오프셋을 이용해 특정 키를 쉽게 찾을 수도 있다.
* SS테이블은 데이터베이스가 고장나면 아직 디스크에 기록되지 않고 메모리의 멤테이블(Memtable)에 머물러있는 최신 데이터들이 손실된다.
* 손실을 방지하기 위해서는 쓰기를 즉시 추가할 수 있는 분리된 로그를 디스크에 유지해야 한다.

### 기타 색인 구조

* 색인 안에 값 저장:
  * 키는 질의가 검색하는 대상.
  * 값은 질의가 찾는 데이터거나 다른 곳의 데이터를 가리키는 참조가 될 수 있다.
  * 실제 데이터를 힙 파일(heap file)에 저장하고, 각 색인은 힙 파일의 데이터 위치만 참조한다.
* 다중 칼럼 색인:
  * 여러 개의 키에 색인을 적용할 수 있다.
  * 가장 일반적인 유형은 결합 색인(concatenated index)이다.
  * 결합 색인은 하나의 칼럼에 다른 칼럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순 결합한다.
* 전문 검색과 퍼지 색인:
  * 유사한 키(오타 등)에 대해 검색하기 위해 퍼지 검색 기술을 사용한다.
  * 전문 검색 엔진의 경우 특정 단어를 검색할 때 해당 단어의 동의어로 질의를 확장한다.

## 트랜잭션 처리나 분석?

* 트랜젝션 처리는 클라이언트가 지연 시간이 낮은 읽기와 쓰기를 가능하게 한다는 의미.
  * 반대로는 주기적으로 실행되는 일괄 처리 작업(배치 잡)이 있다.
  * 옛날에는 데이터베이스를 주로 상거래에 사용했기 때문에 트랜잭션이라는 용어를 사용했다.
  * 이러한 접근 패턴을 온라인 트랜잭션 처리(Online Transaction Processing, OLTP)라고 한다.
* 처음에는 트랙잭션 처리와 분석 질의를 위해 동일한 데이터베이스를 사용했다.
* 데이터가 방대해지자 분석을 위한 개별 데이터베이스를 만들었다:
  * 많은 회사들이 분석을 위한 개별 데이터베이스를 만들었으며, 이를 데이터 웨어하우스라고 불렀다.
  * 이러한 접근 패턴은 OLTP와 구별하기 위해 온라인 분석 처리(Online Analytic Processing, OLAP)라고 한다.

### 데이터 웨어하우징

![](https://user-images.githubusercontent.com/6410412/135793800-b4a20c9c-7ac9-40a3-ab5d-2d9167485e3d.png)

* 개별 데이터 웨어하우스를 사용하는 큰 장점은 분석 접근 패턴에 맞게 최적화할 수 있다는 점이다.
* 데이터 웨어하우스와 OLTP 데이터베이스는 둘 다 SQL 인터페이스를 지원하기 때문에 비슷해 보이지만, 내부는 서로 다른 질의 패턴에 맞게 최적화됐기 때문에 완전히 다르다.

### 분석용 스키마: 별 모양 스키마와 논꽃송이 모양 스키마

* 분석 영역의 데이터 모델은 트랜잭션 처리 영역과 다르게 다양성이 훨씬 적다.
* 많은 데이터 웨어하우스가 별 모양 스키마로 알려진 정형화된 방식을 사용한다.
  ![](https://user-images.githubusercontent.com/6410412/135794012-2fb23638-062f-4e98-8f46-5300ec969fd7.png)
  * 사실 테이블(fact table): 특정 시각에 발생한 이벤트의 집합.
  * 차원 테이블(dimension table): 사실 테이블의 일부 컬럼이 외래키로 가리키는 테이블. (이벤트의 속성을 나타낸다.)
  * 별 모양이라는 이름은 테이블 관계를 시각화했을 때 중앙에 있는 사실 테이블을 차원 테이블로 둘러싸고 있는 모습에서 비롯됐다.
* 눈꽃송이 모양 스키마는 별 모양 스키마의 차원을 더욱 세분화하여 변형한 템플릿이다.

## 칼럼 지향 저장소

* 테이블의 데이터가 방대해지면 효율적으로 저장하고 질의하기 어려워진다.
* 칼럼 지향 저장소는 값을 로우 단위가 아닌 칼럼 단위로 저장하는 방식이다.
* 칼럼 지향 저장소 배치는 각 칼럼에 포함된 로우가 모두 같은 순서인 점에 의존한다.
* 데이터를 압축하면 데이터 처리량을 더 줄일 수 있으며, 데이터 웨어하우스에서 특히 효과적인 방법은 비트맵 부호화다.