cleanUrl: /data-intensive/storage-and-retrieval
share: true

DB는 기본적으로 두가지 일을 수행한다. 데이터를 받으면 저장하고, 후에 요청하면 다시 데이터를 제공한다. 이 챕터는 데이터를 저장하는 방법과 요청하는 방법에 대해 살펴보는데 이것을 알아두어야 하는 이유는 개발자는 처음부터 저장소 엔지는 구현하는 것이 아닌 사용 가능한 여러 저장소 엔진 중에서 개발해야 하는 application 에 적합한 엔진을 선택하는 것이 중요하다.

이번 장은 익숙한 RDB, NoSQL 등의 저장소 엔진을 다룬다. 그리고 로그 구조(log-structured) 계열 저장소 엔진과 B-tree 같은 페이지 지향(page-oriented) 계열 저장소를 검토한다.

<script async src="<https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js>"></script>
<ins class="adsbygoogle"
     style="display:block; width: 100%;"
     data-ad-format="fluid"
     data-ad-layout-key="-fb+5w+4e-db+86"
     data-ad-client="pub-8946038251809377"
     data-ad-slot="5490836264"></ins>
<script>
     (adsbygoogle = window.adsbygoogle || []).push({});
</script>

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

매우 간단한 형태의 DB를 bash 함수로 구현했다.

#!/bin/bash

db_set() {
	echo "$1, $2" >> database
}

db_get() {
	echo "^$1, " database | sed -e "s/^$1,//" | tail -n 1
}

key-value 저장소의 함수이며 데이터가 저장되며 다음과 같이 실행된다.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ec03ca32-427c-493e-bc42-d01eccfb8ded/Screen_Shot_2021-04-03_at_7.05.10.png

db_set 을 호출할 때 마다 끝에 추가하므로 키를 여러번 갱신해도 예전 값을 덮어 쓰지 않으며, 최신 값은 키의 가장 마지막 항목을 살펴봐야 한다. (tail -n 1 을 실행하는 이유)

이러한 파일에 추가 작업은 매우 효율적이기 때문에 꽤 좋은 성능을 보여주고 많은 DB가 내부적으로 추가 전용 로그를 사용한다. 물론 실제 DB 라면 다뤄야 할 더 많은 문제가 있다. (동시성 제어, 로그가 영원히 사라지지 않게끔 디스크 공간 회수, 오류 처리, 부분적으로 기록된 레코드 처리 등등)

반면, db_get 은 record 가 많아질 수록 성능이 좋지 않다. key 를 찾기 위해 로그를 전부 봐야 하므로 $O(n)$ 이 된다. 레코드 수가 두배 늘면 검색도 두배 오래 걸리는 것이다.

여기서 index 가 나온다.

특정 키의 값을 효율적으로 찾기 위해 필요한 것이 색인 이다.

해시 색인 (Hash index)