Project Overview

본 프로젝트는 제공된 인메모리 스토리지 프레임워크를 기반으로, 데이터베이스의 핵심 인덱스 자료구조인 SkipList와 B+Tree를 직접 설계하고 구현한 프로젝트입니다.

주요 작업물 (직접 구현)

• In-Memory-Indexing/skiplist/skiplist.cc, In-Memory-Indexing/skiplist/memdb.cc : LSM-Tree 구조의 MemTable 로직 구현
• In-Memory-Indexing/bptree/bptree.h, In-Memory-Indexing/bptree/bptree.cc : In-place Update 방식의 B+Tree 엔진 구현

---

Implementation Details

1. SkipList-based MemTable (LSM-Tree)

LSM-Tree의 Write Buffer(MemTable) 역할을 수행하며, 논리적 삭제 및 버전 관리를 지원하는 구조입니다.

• 주요 파일: In-Memory-Indexing/skiplist/skiplist.cc, In-Memory-Indexing/skiplist/memdb.cc
• 핵심 기능: Tombstone 메커니즘, Random Level 기반 자가 균형, Mutable/Immutable MemTable 관리 정책

2. B+Tree Indexing Engine

압도적인 탐색 성능과 데이터 무결성을 보장하는 고성능 인덱싱 엔진입니다.

• 주요 파일: In-Memory-Indexing/bptree/bptree.h, In-Memory-Indexing/bptree/bptree.cc
• 핵심 기능: 하향식 탐색 및 삽입, 상향식 노드 분할(Split), Underflow 시 형제 노드 차용(Borrow) 및 병합(Merge)

---

💻 빌드 및 컴파일

bptree, skiplist 디렉토리에서 Makefile을 통해 빌드 및 테스트를 수행합니다.

# 1. 기존 빌드 파일 삭제
make clean

# 2. 소스코드 컴파일 및 실행 파일 생성
make

# 3. GoogleTest 기반 통합 테스트 실행
./memdb_test

📁 Directory Structure

• In-Memory-Indexing/
  • 📂 bptree/bptree.h & bptree/bptree.cc: B+Tree 아키텍처 및 핵심 알고리즘 수록
  • 📂 skiplist/skiplist.cc & skiplist/memdb.cc: SkipList 기반 MemTable 및 메모리 관리 로직 수록
• googletest/: 유닛 테스트를 위한 프레임워크

🚀 RocksDB-Core Implementation

본 프로젝트는 RocksDB의 아키텍처를 벤치마킹하여, LSM-Tree 기반의 고성능 스토리지 엔진을 직접 설계하고 구현한 프로젝트입니다.

🔥 주요 작업물 (직접 구현)

• RocksDB-Core/memdb.cc : LSM-Tree 구조의 MemTable 로직 구현
• RocksDB-Core/sstable.cc : 디스크 기반 영속성 저장을 위한 SSTable 엔진 구현
• RocksDB-Core/bloom_filter.cc : 데이터 탐색 속도 최적화를 위한 Bloom Filter 구현
• RocksDB-Core/compaction.cc : 데이터 압축 및 병합을 위한 Compaction 로직 구현

---

🛠️ Implementation Details

1. MemTable & SSTable

LSM-Tree의 Write Buffer인 MemTable과 디스크에 데이터를 영속적으로 저장하는 SSTable을 구현했습니다.

• 주요 파일: RocksDB-Core/memdb.cc, RocksDB-Core/sstable.cc
• 핵심 기능: 데이터의 순차적 로깅, 메모리에서 디스크로의 Flush 메커니즘

2. Bloom Filter & Compaction

검색 성능 향상을 위한 필터링 기법과 데이터 무결성 및 저장 공간 효율을 위한 압축 엔진입니다.

• 주요 파일: RocksDB-Core/bloom_filter.cc, RocksDB-Core/compaction.cc
• 핵심 기능: 오탐지 최소화, 다중 계층 데이터 병합(Compaction), 읽기 I/O 최적화

---

💻 빌드 및 컴파일

RocksDB-Core 디렉토리에서 Makefile을 통해 빌드 및 테스트를 수행합니다.

# 1. 기존 빌드 파일 삭제
make clean

# 2. 소스코드 컴파일 및 실행 파일 생성
make

# 3. 테스트 실행
./db_test

📁 Directory Structure

• RocksDB-Core/
  • 📂 memdb.cc : MemTable 관리 및 로직
  • 📂 sstable.cc : SSTable 데이터 처리 및 저장 로직
  • 📂 bloom_filter.cc : 인덱스 탐색 가속화 로직
  • 📂 compaction.cc : Compaction 관리 정책
• googletest/: 유닛 테스트를 위한 프레임워크