지난 글에서 정리했듯 BST 는 on-disk 자료구조로는 적합하지 않았다.그래서 BST 를 기반으로 fanout 이 크고 트리의 높이도 더 작은 B-Tree 라는 자료구조가 등장했다.이번 글에서는 제일 기본적인 B-Tree 에 대해 정리해본다. B-Tree 를 그림으로 표현하면 아래와 같이 표현할 수 있다. 또는 책에 따라서 아래와 같이 표현하기도 한다. B-Tree 내부 각 노드가 보유한 key 값들은 일정한 순서로 정렬되어 있다.(위 그림의 경우라면 key1 따라서 하나의 노드 안에서 특정 키를 찾을 때는 이분 탐색을 사용하여 원하는 키를 찾을 수 있다. 꼭 노드 내부가 아니더라도, B-Tree 의 데이터 탐색 시간복잡도는 로그 시간복잡도를 갖는다.예를 들어 40억개 데이터 중에서 원하는 데이터..
이번 글부터는 가장 유명한 저장 구조인 B-Tree 를 이해하는데 있어 필요한 기본적인 개념들을 정리한다.지난 글에서도 언급했듯 B-Tree 는 mutability 를 갖는 저장 구조이다.그리고 대부분의 mutability 구조는 in-plcae update 메커니즘을 사용한다.이 말은 데이터를 삽입, 수정, 삭제하는 연산을 수행할 때, 그 데이터가 저장된 그 파일 안에서 연산이 일어난다는 것을 말한다. 어떤 스토리지 엔진은 같은 데이터 레코드의 여러 버전을 동시에 저장하기도 한다.다중 버전 동시성 제어, Slotted Page 가 그 예시이다.하지만 이해를 간단히 하기 위해, B-Tree 를 정리할 때는 하나의 데이터 레코드가 저장된 위치는 유일하다고 가정하자. Binary Search TreeB-Tr..
스토리지 엔진은 특정 자료구조를 기반으로 만들어진다.하지만 캐싱, 복구, 트랜잭션과 같은 기능은 이런 자료구조가 설명해주지 않는다. 스토리지 구조에는 크게 3가지 공통 변수가 있다. 1. buffering 사용 여부2. immutable file 또는 mutable file 사용3. 데이터 저장시 정렬 여부 스토리지 구조가 갖는 최적화 방법과 구별 기준 대부분은 이 3가지 개념 중 하나와 관련되어 있다. Buffering스토리지 구조가 디스크에 데이터를 저장하기 전에 특정 양의 데이터를 모았다가 저장하는지 아닌지를 나타낸다.물론 모든 디스크 기반 구조는 어느정도 버퍼링 기법을 사용할 수 밖에 없다.디스크가 최소한 block 단위로 데이터를 전달하므로, 블록 데이터를 모았다가 쓰는 것이 좋기 때문이다.따라..
개요이제 스토리지 엔진이 어떻게 데이터를 저장되는지 정리하기에 앞서, data file 과 index file 에 대해 정리해보려고한다.우리는 왜 데이터를 단순히 파일 시스템이 아니라 DBMS 를 사용해서 저장할까? DBMS도 데이터를 저장할 때 파일로 저장하지만, DBMS 는 파일 시스템이 제공하는 디렉토리 / 파일의 계층 구조를 사용하지 않는다.또한 파일을 만들 때도 DBMS에서 직접 결정한 포맷에 맞춰 파일을 구성한다.이렇게 하는 이유는 크게 3가지 이유가 있다. 1. Storage EfficiencyDBMS는 데이터 레코드를 저장할 때 storage overhead 를 최소화하는 방식으로 파일을 구성한다. 2. Access Efficiency원하는 레코드를 찾을 때 최소한의 단계를 거쳐서 찾을 수..
이번 글에서는 다양한 관점에서 DBMS 를 분류해보려고 한다.DBMS 를 분류하는데는 다양한 관점이 있지만 특히 중간 스토리지와 레이아웃 관점에서 분류해보려고 한다.(다만 DBMS가 각 관점에서 딱 잘라 분류되지는 않을 수 있다는 점을 염두해두자.) 이 두가지 관점 외에도 다음의 기준으로 3가지로 DBMS를 분류하는 방법도 있다. 1. OLTP (online transaction processing) database대량의 사용자 요청과 트랜잭션을 처리하며, 빠르게 실행되는 사전 정의된 쿼리를 자주 사용한다. 보통 웹 개발할 때 사용하는 DBMS 가 속한다고 이해했다.예를 들어 로그인 기능을 구현할 때 사용자를 조회하는 경우, 사용자 조회 쿼리는 사전에 개발자에 의해 정의되어있으며, 상대적으로 실행시간이 ..
DBMS 는 서로 다른 목적 하에 동작한다.어떤 DBMS 는 임시적인 hot data 를 처리하는데 사용되고, 어떤 DBMS 는 영구적인 cold storage 를 처리하는데 사용된다.어떤 DBMS 는 복잡한 쿼리를 통해 데이터에 접근할 수 있고, 어떤 DBMS 는 오직 key 값을 가지고 데이터에 접근한다.어떤 DBMS 는 시간순으로 들어오는 데이터를 처리하는데 유리하고, 어떤 DBMS 는 매우 큰 blob 데이터를 처리하는데 유리하다. 이런 DBMS 의 차이를 이해하기 위해서는 DBMS 의 아키텍처와 다양한 관점에서의 DBMS 분류에 대해 이해할 필요가 있다.먼저 이번 글에서는 데이터베이스 아키텍처와 스토리지 엔진에 대해 간단하게 알아본다. 데이터베이스 아키텍처DBMS 시스템에 대한 공통적인 청사진은..
