이번 글부터는 가장 유명한 저장 구조인 B-Tree 를 이해하는데 있어 필요한 기본적인 개념들을 정리한다.지난 글에서도 언급했듯 B-Tree 는 mutability 를 갖는 저장 구조이다.그리고 대부분의 mutability 구조는 in-plcae update 메커니즘을 사용한다.이 말은 데이터를 삽입, 수정, 삭제하는 연산을 수행할 때, 그 데이터가 저장된 그 파일 안에서 연산이 일어난다는 것을 말한다. 어떤 스토리지 엔진은 같은 데이터 레코드의 여러 버전을 동시에 저장하기도 한다.다중 버전 동시성 제어, Slotted Page 가 그 예시이다.하지만 이해를 간단히 하기 위해, B-Tree 를 정리할 때는 하나의 데이터 레코드가 저장된 위치는 유일하다고 가정하자. Binary Search TreeB-Tr..

데이터베이스 스터디를 하며 인덱스를 내용을 공부하고 발표한 뒤, covering index 에 대한 질문을 받았다.스터디 책에서는 data file 을 구현하는 방법 중에 모든 데이터 레코드가 인덱스 파일에 들어있는 index-organized tables (IOT) 방식을 소개하고 있었는데, IOT 와 covering index 가 같은 개념인지 묻는 질문이었다.covering index 개념을 처음 들어봐서 다른 분의 답변을 듣고 공부할 수 있었는데, 새로 알게된 개념인만큼 이번 기회에 정리해보려고 한다. Covering Indexcovering 은 포괄한다는 의미를 갖고 있다.인덱스는 테이블 데이터를 찾을 때 사용할 일부 컬럼에 대한 데이터를 갖고 있는데, 이 데이터만으로 쿼리를 커버할 수 있는 인..

스토리지 엔진은 특정 자료구조를 기반으로 만들어진다.하지만 캐싱, 복구, 트랜잭션과 같은 기능은 이런 자료구조가 설명해주지 않는다. 스토리지 구조에는 크게 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 시스템에 대한 공통적인 청사진은..

벌써 4월이 끝나가고 있다.아무것도 안한 것 같은데 시간이 이렇게 빨리 지났다는 것이 신기하다.아직 4월이 다 지나지는 않았지만, 주말이 아니면 회고를 쓸 시간이 없을 것 같아서 이번 달에도 미리 써본다. 이번 달에는 2025년 목표를 다시 돌아보면서 이번 달에 무엇을 했고, 느꼈는지 정리해보려고 한다. 진로 관련 목표전공1. 졸프드디어 오픈소스 읽기를 어느 정도 마무리하고 구현을 시작했다.사실 오픈소스를 100% 이해한 것은 아니지만, 코드를 읽으면서 복잡한 구조를 통으로 이해하고 구현하기보다, 작은 단위로 이해하고 구현하는 것을 반복해야겠다고 느꼈다.(소공에서 나온 개념으로 비유하면 incremental development 방식으로..) 나는 CREATE 구문에 대한 구현을 맡았다.파서가 CREA..

https://www.acmicpc.net/problem/14868 풀이 과정시드마이어의 문명과 비슷한 게임을 구현하는 시뮬레이션 문제문명이 건설되었을 때, 시간이 지남에 따라 점점 퍼지다가 두 문명이 인접하면 하나의 문명으로 합쳐진다.이때 모든 문명이 하나로 합쳐지기까지 걸리는 시간을 구하는 문제이다. 문명이 건설되었을 때 퍼지는 것은 BFS로 구현할 수 있고, 문명을 하나의 그룹으로 합치는 것은 분리집합으로 구현할 수 있다.(분리집합을 사용하지 않고도 풀 수 있다는데, 그렇게는 안 풀어봤다.) from collections import dequeimport sysinput = sys.stdin.readlinedef find(x): if parent[x] == x: return x ..

지난 글에서는 뉴럴 네트워크와 역전파에 대해 정리하였다. 뉴럴 네트워크는 기계학습에서 학습시키는 함수의 새로운 형태로, 여러 단위 함수의 중첩함수 형태이다.뉴럴 네트워크를 학습시킬 때도 로스를 구해서 로스의 값이 줄어드는 방향으로 학습시키게 되는데, 경사하강법을 사용하는 경우 미분 값이 필요하다. 여러 함수들이 합성된 뉴럴 네트워크에서 미분값을 구하기 위해, 데이터를 넣어서 전체 값을 계산하는 추론 과정과, 해당 값을 이용해서 각 레이어의 미분값을 구하는 학습 과정이 일어난다.학습 과정에서는 역전파를 통해 각 레이어의 미분값을 구해두고, 업데이트 하려는 값에 대해서만 미분값을 활용하여 경사하강법과 같은 방식으로 다음 w 값을 업데이트 한다. 이번 글에서는 CNN 에 대해서 정리해보려고 한다.사실 딥러닝..

Configuration Management (CM)CM은 소프트웨어 시스템의 변화를 관리하는 도구, 프로세스, 정책과 관련된 개념이다.특히 팀 프로젝트를 하다보면 각 개발자들이 서로 다른 변화를 만들어내기 때문에 이 변화들을 관리하기 위해 필수적이다. 소프트웨어 컴포넌트의 확정된 변경사항은 버전별로 repository 라는 공동 저장소에 저장되어 있고, 개발자들은 repository 에 있는 코드를 자신의 workspace 로 가져와서 개발한다. CM 에서 수행하는 활동은 크게 4가지가 있다. 1. version management시스템 컴포넌트를 버전 별로 추적 관리하는 것 2. system building컴포넌트, 데이터, 라이브러리를 모아서 하나의 실행가능한 프로그램으로 만드는 것 3. chan..