가장 간단한 데이터베이스 구현

모든 애플리케이션 소프트웨어 중에서 데이터베이스가 가장 복잡할 수 있습니다.

MySQL 매뉴얼은 3,000페이지가 넘고, PostgreSQL 매뉴얼은 2,000페이지가 넘으며, Oracle 매뉴얼은 모두 합친 것보다 훨씬 더 두껍습니다.

하지만 가장 간단한 데이터베이스를 직접 작성하는 것은 어렵지 않습니다. Reddit에는 단 몇 백 단어로 원리를 명확하게 설명하는 게시물이 있습니다. 아래는 이 포스팅을 토대로 제가 정리한 내용입니다.

1. 데이터를 텍스트 형식으로 저장

첫 번째 단계는 저장할 데이터를 텍스트 파일에 쓰는 것입니다. 이 텍스트 파일은 데이터베이스입니다.

읽기 쉽도록 데이터를 레코드로 나누어야 하며, 각 레코드의 길이를 동일하게 지정해야 합니다. 예를 들어, 각 레코드의 길이가 800바이트라고 가정하면 다섯 번째 레코드의 시작 위치는 3200바이트입니다.

대부분의 경우 특정 레코드의 위치는 모르고 기본 키의 값만 알고 있습니다. 이때, 데이터를 읽기 위해서는 기록을 하나씩 비교하면 됩니다. 그러나 이는 너무 비효율적입니다. 실제 애플리케이션에서는 데이터베이스가 데이터를 저장하기 위해 B-트리 형식을 사용하는 경우가 많습니다.

2. B-트리란 무엇인가요?

B-트리를 이해하려면 이진 검색 트리부터 시작해야 합니다.

이진 검색 트리는 검색 효율성이 매우 높은 데이터 구조입니다.

(1) 각 노드에는 최대 2개의 하위 트리가 있습니다.

(2) 왼쪽 하위 트리는 상위 노드보다 작은 값을 갖고, 오른쪽 하위 트리는 상위 노드보다 큰 값을 갖습니다.

(3) n개의 노드 중에서 목표값을 찾으려면 일반적으로 log(n) 비교만 필요합니다.

이진 검색 트리의 구조는 검색 효율성이 레벨 수와 관련되어 있기 때문에 데이터베이스에는 적합하지 않습니다. 데이터가 낮을수록 더 많은 비교가 필요합니다. 극단적인 경우에는 n개의 데이터에서 목표 값을 찾기 위해 n번의 비교가 필요합니다. 데이터베이스의 경우 레이어에 들어갈 때마다 하드 디스크에서 데이터를 읽어야 하는데, 이는 데이터베이스가 읽는 횟수가 적을수록 하드 디스크를 읽는 시간이 훨씬 길어지기 때문에 매우 치명적입니다. 하드디스크는 더 좋습니다.

B-트리는 이진 검색 트리를 개선한 것입니다. 여러 데이터를 한 번에 읽을 수 있고 하드 디스크 작업 횟수를 줄일 수 있도록 관련 데이터를 최대한 모으는 것이 디자인 아이디어입니다.

B-tree에도 세 가지 특징이 있습니다.

(1) 노드는 여러 값을 보유할 수 있습니다. 예를 들어 위 그림에서 가장 큰 노드는 4개의 값을 보유합니다.

(2) 데이터가 채워지지 않으면 새 레이어가 추가되지 않습니다. 즉, B-트리는 가능한 한 적은 "레이어"를 추구합니다.

(3) 하위 노드의 값은 상위 노드의 값과 엄격한 크기 대응을 갖습니다. 일반적으로 상위 노드에 값이 있으면 +1개의 하위 노드가 있습니다. 예를 들어, 위 그림에서 부모 노드는 두 개의 값(7과 16)을 가지며, 이는 세 개의 자식 노드에 해당합니다. 첫 번째 자식 노드는 7보다 작은 값을 갖고, 마지막 자식 노드는 16보다 큰 값을 갖습니다. , 중간 자식 노드는 7에서 16 사이의 값입니다.

이 데이터 구조는 하드 디스크에서 읽는 횟수를 줄이는 데 매우 유용합니다. 노드가 100개의 값을 보유할 수 있다고 가정하면 3계층 B-트리는 100만 개의 데이터를 보유할 수 있습니다. 이진 검색 트리로 대체되면 20개의 계층이 필요합니다. 운영 체제가 한 번에 하나의 노드를 읽고 루트 노드가 메모리에 남아 있다고 가정하면 B-트리는 100만 개의 데이터 중에서 목표 값을 찾기 위해 하드 디스크를 두 번만 읽으면 됩니다.

3. 인덱스

데이터베이스는 B-트리 형식으로 저장되어 "기본 키"에 따라 데이터를 찾는 문제만 해결합니다. 다른 필드를 찾으려면 색인을 생성해야 합니다.

소위 인덱스는 특정 필드를 키로 갖는 B-트리 파일입니다. 직원 번호(기본 키)와 이름이라는 두 개의 필드를 포함하는 "직원 테이블"이 있다고 가정합니다. 이름에 대한 색인 파일을 생성할 수 있습니다. 이 파일은 이름을 B-트리 형식으로 저장하며, 각 이름 뒤에는 데이터베이스에서의 위치(즉, 어떤 레코드)가 옵니다. 이름을 검색할 때는 먼저 색인에서 해당 레코드를 찾은 다음 테이블에서 읽어옵니다.

이러한 인덱스 검색 방식을 "Indexed Sequential Access Method", 줄여서 ISAM이라고 합니다. 이미 여러 가지 구현(예: C-ISAM 라이브러리 및 D-ISAM 라이브러리)이 있습니다. 이러한 코드 라이브러리를 사용하는 한 가장 간단한 데이터베이스를 직접 작성할 수 있습니다.

4. 고급 기능

가장 기본적인 데이터 액세스(인덱싱 포함)를 배포한 후 일부 고급 기능도 구현할 수 있습니다.

(1) SQL 언어는 데이터베이스의 범용 운영 언어이므로 SQL 명령을 해당 ISAM 작업으로 구문 분석하려면 SQL 파서가 필요합니다.

(2) 데이터베이스 연결(조인)이란 "외래 키"를 통해 데이터베이스의 두 테이블 사이에 연결 관계를 설정하는 것을 말합니다. 이 작업을 최적화해야 합니다.

(3) 데이터베이스 트랜잭션은 일괄적으로 수행되는 일련의 데이터베이스 작업을 말하며 한 단계가 실패하면 전체 작업이 실패하게 됩니다. 따라서 작업이 실패할 경우 롤백할 수 있도록 "작업 로그"가 필요합니다.

(4) 백업 메커니즘: 데이터베이스 복사본을 저장합니다.

(5) 원격 작업: 사용자가 TCP/IP 프로토콜을 통해 다른 컴퓨터에서 데이터베이스를 작업할 수 있습니다.