지난 글에서 정리했듯 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 시스템에 대한 공통적인 청사진은..
자바스크립트의 함수는 다른 언어의 함수와 마찬가지로 코드의 묶음으로도 역할을 하지만, 모듈화 / 클로저 / 객체 생성 등의 역할을 하기도 한다. 자바스크립트에서 함수를 생성하는 방법은 3가지가 있다. 1. 함수 선언문 함수 리터럴 형태로 함수를 선언한다. function func(a, b) { return a + b; } // use function var result = func(1,2); // result = 3 function 키워드, 함수 이름, 매개변수와 함수 몸체로 구성된다. 함수 이름은 원래 생략하여 익명함수로도 리터럴 함수를 생성할 수 있지만, 함수 선언문 방식으로 함수를 선언할 때는 함수 이름을 반드시 입력해야한다. ( 보통 익명함수는 콜백함수를 인자로 넘길 때 많이 사용한다. ) // ..
기본타입 = 숫자, 문자열, 불린값 각 기본타입은 객체가 아님에도 각 타입에 맞는 메서드를 갖고 있다. 이때는 메서드 호출시 순간적으로 기본타입을 참조타입으로 바꾸었다가 메서드 호출이 끝나면 다시 기본타입으로 바뀌게 된다. + 연산자 자바스크립트의 + 연산자는 (숫자) + (숫자) 만 숫자 연산으로 계산하고, (숫자) + (문자열) 이나 (문자열) + (문자열) 은 문자열 연결로 계산한다. typeof 연산자 피연산자의 타입을 문자열 형태로 리턴한다. 이때 null 타입은 'object' 로 출력하고, 함수 타입은 'function' 으로 출력하는 부분에 주의한다. 배열은 'object'로 출력한다. == 연산자와 === 연산자 == 연산자는 두 피연산자의 타입이 다를 경우, 타입변환을 거친 다음 비교하..
-배열 자바스크립트의 배열은 C의 배열과는 조금 다르다. 오히려 파이썬의 리스트에 더까운데, 그렇다고 파이썬의 리스트와 완전히 같은 것도 아니다. 배열의 생성은 배열 리터럴이나 생성자 함수를 이용한다. 배열 리터럴은 [] 를 이용하여 표기한다. 파이썬과 똑같다. var a = ['apple', 10, true]; 위와 같이 데이터 형이 통일 되지 않아도 된다. 배열 요소에 접근하여 읽고 쓸 때도, 배열 내 위치 인덱스 값을 이용해 [] 로 접근한다. a[0] = 'orange'; console.log(a[0]); // orange 여기까지는 파이썬의 리스트와 다를 게 없어보인다. 그러나 자바스크립트 배열의 특이한 점은 배열에 동적으로 값을 넣을 때, 인덱스를 신경쓰지 않고 넣을 수 있다는 점이다. var..
-프로토타입 모든 객체는 각자 부모 역할을 하는 객체를 갖고 있는데, 이 객체를 프로토타입이라고 한다. 객체지향 프로그래밍의 '상속'과 유사하다. 간단하게 객체를 만들어서 출력해보았다. 책이 옛날 책이라 그런지, 책 내용과는 달리 크롬에서도 __proto__ 가 아니라 [[Prototype]] 프로퍼티가 보인다. ECMAScript 명세서에 의하면, 모든 자바스크립트 객체는 자신의 프로토타입 객체를 가리키는 [[Prototype]] 프로퍼티를 가진다. 이 프로토타입 객체의 종류는 여러가지가 있는데, 어떤 종류의 객체를 프로토타입으로 가질지는 사바스크립트 룰에 따라 객체를 생성할 때 결정된다. 예시와 같이 객체 리터럴로 생성한 객체는 Object.prototype 객체를 프로토타입 객체로 가진다. 근데 한..
