5조 물리적 데이터베이스 미션
B-tree는 1972년 Rudolf Bayer와 Ed McCreight에 의해 제안된 자료 구조입니다. 그 등장은 데이터베이스와 파일 시스템에서 대량의 데이터를 효율적으로 관리하기 위한 필요에서 비롯되었습니다. 일반적인 이진 트리는 삽입, 삭제, 탐색이 평균적으로 O(log n)의 시간이 걸리지만, 데이터가 디스크에 저장되는 경우 이진 트리는 노드의 깊이가 깊어질수록 성능이 급격히 저하됩니다. B-tree는 이러한 문제를 해결하기 위해 설계되었습니다. 이는 노드의 자식이 여러 개일 수 있도록 하여 트리의 높이를 낮추고, 디스크 I/O 횟수를 줄여 성능을 개선합니다.
B-tree는 자식 노드가 여러 개 있는 자가 균형 이진 탐색 트리입니다. B-tree의 각 노드는 여러 개의 키를 가지고 있으며, 각 키는 자식 노드를 가리킵니다. B-tree의 중요한 특징은 다음과 같습니다:
- 모든 리프 노드는 동일한 깊이에 있습니다.
- 노드의 키 개수는 미리 정해진 범위 내에서 유지됩니다.
- 삽입과 삭제 시 트리는 자동으로 균형을 유지하며, 이 과정에서 노드 분할(Split)이나 병합(Merge)이 일어날 수 있습니다.
B-tree와 B+ tree는 유사한 구조를 가지지만, 몇 가지 차이가 존재합니다:
- B-tree: 내부 노드와 리프 노드 모두 데이터와 키를 가집니다. 이로 인해 데이터 검색 시 중간 노드에서 데이터를 바로 찾을 수 있습니다.
- B+ tree: 모든 데이터는 리프 노드에만 저장됩니다. 내부 노드는 키와 포인터만을 포함하며, 데이터 검색은 반드시 리프 노드에서 이루어집니다. 또한 리프 노드들은 Linked List 형태로 연결되어 있어 순차적인 데이터 접근에 효율적입니다.
Clustered Index는 테이블의 데이터가 인덱스의 순서대로 물리적으로 정렬되는 인덱스입니다. 기본적으로 테이블에서 하나의 Clustered Index만 생성할 수 있으며, 인덱스 키가 테이블의 레코드를 결정합니다. Clustered Index는 데이터 검색 속도를 크게 향상시키며, 특히 범위 검색에 효과적입니다.
Clustered Index에서는 데이터가 인덱스의 순서에 따라 디스크에 물리적으로 정렬됩니다. 예를 들어, Primary Key로 Clustered Index를 생성하면, 테이블의 데이터는 Primary Key 순서에 따라 저장됩니다. 이로 인해, 인덱스 탐색은 곧 데이터 자체를 탐색하는 과정이 되어, 추가적인 디스크 I/O를 줄이고, 검색 속도를 향상시킵니다.
테이블을 저장하는 방식에는 다양한 방법이 존재합니다. 이들은 데이터의 구조와 액세스 패턴에 따라 최적의 성능을 제공할 수 있습니다:
- Heap Table: 데이터가 정렬되지 않은 상태로 테이블에 저장됩니다. 이 방식은 데이터의 삽입이 빠르지만, 검색 성능은 떨어질 수 있습니다.
- Clustered Index Table: 데이터가 인덱스 키 순서에 따라 정렬되어 저장됩니다. 검색 성능이 우수하며, 범위 쿼리에 특히 유리합니다.
- Partitioned Table: 테이블을 여러 파티션으로 나누어 저장합니다. 이는 대용량 데이터를 처리할 때 성능을 최적화하고 관리의 편의성을 제공합니다.
물리적으로 테이블을 저장하는 방식에는 다음과 같은 방법들이 있습니다:
- Row-oriented Storage: 데이터가 행(row) 단위로 저장됩니다. 전통적인 데이터베이스 시스템에서 사용되며, 트랜잭션 처리와 같이 행 단위 작업에 적합합니다.
- Column-oriented Storage: 데이터가 열(column) 단위로 저장됩니다. 대량의 데이터를 분석할 때 주로 사용되며, 특정 열에 대한 쿼리가 많을 때 효율적입니다.
- File-based Storage: 데이터베이스가 아닌 단순 파일 시스템에 데이터를 저장하는 방법입니다. 텍스트 파일, CSV 파일, 또는 JSON 파일 등으로 데이터를 저장할 수 있습니다.
InnoDB는 MySQL의 기본 스토리지 엔진으로, ACID 트랜잭션을 지원하고, 외래 키 제약 조건을 관리하며, 자동 복구 기능을 제공합니다. InnoDB는 B+ 트리 기반의 인덱스를 사용하여 데이터를 효율적으로 검색하며, Clustered Index를 기본으로 사용합니다.
- Create Database: 데이터베이스가 생성되면, InnoDB는 해당 데이터베이스를 위한 디렉토리를 생성하고, 필요한 시스템 테이블과 관련 메타데이터를 초기화합니다.
- Create Table: 테이블이 생성될 때, InnoDB는 테이블의 구조를 메타데이터에 저장하고, 테이블에 대한 Clustered Index를 생성합니다. 만약 명시적으로 인덱스를 정의하지 않았다면, Primary Key 또는 유니크한 칼럼을 기반으로 Clustered Index를 생성합니다.
MySQL에서 사용할 수 있는 주요 스토리지 엔진들은 다음과 같습니다:
- MyISAM: InnoDB 이전의 기본 스토리지 엔진으로, 트랜잭션을 지원하지 않지만, 빠른 읽기 성능을 제공합니다.
- Memory: 데이터를 메모리에 저장하여 매우 빠른 성능을 제공하지만, 영구 저장은 불가능합니다.
- CSV: 데이터를 CSV 파일로 저장하는 간단한 스토리지 엔진으로, 외부 애플리케이션과의 데이터 교환에 유용합니다.
- Aria: MyISAM의 대체제로, 트랜잭션을 지원하지 않지만 빠른 읽기와 쓰기 성능을 제공합니다.
- TokuDB: 대용량 데이터 처리에 최적화된 스토리지 엔진으로, 높은 압축률과 성능을 제공합니다.
- B-tree Index: 대부분의 일반적인 쿼리에서 사용되는 인덱스로, B-tree 구조를 기반으로 하여 빠른 검색을 제공합니다.
- Hash Index: 정확한 일치 검색에 사용되며, 메모리 스토리지 엔진에서 주로 사용됩니다.
- Full-text Index: 텍스트 기반의 데이터 검색에 사용되며, 자연어 검색을 지원합니다.
- Spatial Index: 공간 데이터 (예: 지리 정보) 처리를 위한 인덱스로, MySQL의 GIS 기능에서 사용됩니다.
- R-tree Index: 공간 데이터에 사용되는 인덱스로, 좌표 기반의 데이터 검색에 최적화되어 있습니다.
지도 정보(지리 정보)를 MySQL에 저장하려면 Spatial 데이터 타입을 사용해야 합니다. MySQL은 POINT, LINESTRING, POLYGON 등의 공간 데이터 타입을 지원하며, 이를 통해 위치 데이터를 저장할 수 있습니다. 또한, 공간 인덱스(Spatial Index)를 사용하여 빠른 지리 정보 검색을 수행할 수 있습니다.
-
Oracle: Oracle은 테이블을
Tablespace라는 논리적 저장소에 저장하며, 테이블은 세그먼트(Segment)라는 단위로 저장됩니다. 데이터는 Row 단위로 저장되며, Index Organized Table을 통해 인덱스와 데이터를 함께 저장하는 방식도 지원합니다. - MS-SQL: MS-SQL Server는 데이터 파일에 데이터를 저장하며, 행 기반의 저장 방식(Rowstore)과 열 기반의 저장 방식(Columnstore)을 모두 지원합니다. Clustered Index가 기본적인 테이블 저장 방식으로 사용됩니다.
- PostgreSQL: PostgreSQL은 데이터를 테이블 공간에 저장하며, 기본적으로 Heap Table 방식을 사용합니다. 또한, TOAST(Tuple Overflow Storage Technique)를 통해 큰 데이터를 효율적으로 저장할 수 있습니다. 인덱스는 B-tree를 기본으로 사용하며, GiST, GIN 등의 다양한 인덱스를 지원합니다.