토픽 76 / 76·비교표
## Part 9: 분산/저장소 자료구조
LSM-Tree vs B+Tree
| 항목 | LSM-Tree | B+Tree |
|---|---|---|
| 쓰기 성능 | 매우 빠름 (순차 쓰기) | 느림 (랜덤 쓰기) |
| 읽기 성능 | 느림 (다중 레벨 검색) | 빠름 (단일 트리) |
| 공간 증폭 | 높음 (중복 키) | 낮음 |
| 쓰기 증폭 | Compaction 오버헤드 | 적음 |
| 적용 | Cassandra, RocksDB, LevelDB | MySQL, PostgreSQL |
Consistent Hashing vs Modular Hashing
| 항목 | Consistent Hashing | Modular Hashing |
|---|---|---|
| 재배치 | 최소 (K/N개만 이동) | 전체 재배치 |
| 노드 추가/제거 | 인접 노드만 영향 | 전체 영향 |
| 부하 균형 | 가상 노드로 해결 | 균등 (정적) |
| 적용 | 분산 캐시 (DynamoDB) | 단일 서버 해시 |
Merkle Tree vs 전체 해시 vs 체크섬
| 항목 | Merkle Tree | 전체 해시 | 체크섬 |
|---|---|---|---|
| 검증 | O(log n) 부분 검증 | O(n) 전체 비교 | 무결성만 |
| 변경 감지 | 변경된 부분만 식별 | 변경 위치 불명 | 단순 오류 |
| 적용 | 블록체인, Git | 파일 비교 | 네트워크 전송 |
CoW B-Tree vs In-place B-Tree vs LSM
| 항목 | CoW B-Tree | In-place B-Tree | LSM-Tree |
|---|---|---|---|
| 수정 방식 | 불변 (경로 복사) | 직접 수정 | 순차 쓰기 |
| 스냅샷 | 무료 (이전 버전 보존) | WAL 필요 | 레벨별 스냅샷 |
| 쓰기 증폭 | 경로 복사 오버헤드 | 낮음 | Compaction |
| 적용 | Btrfs, LMDB | InnoDB, PostgreSQL | RocksDB, LevelDB |
Radix Tree vs Trie vs 해시
| 항목 | Radix Tree | Trie | 해시 |
|---|---|---|---|
| 공간 | 효율적 (엣지 압축) | 비효율 (노드 많음) | 중간 |
| 접두사 검색 | 가능 | 가능 | 불가 |
| 점 검색 | O(m) | O(m) | O(1) 평균 |
| 적용 | Linux 라우팅, Redis | 사전 | 범용 |
Rope vs String vs Gap Buffer
| 항목 | Rope | String | Gap Buffer |
|---|---|---|---|
| 편집 | O(log n) | O(n) | O(1) 지역 |
| 구조 | 균형 이진 트리 | 연속 배열 | 갭 포함 배열 |
| 적용 | 대용량 텍스트 에디터 | 일반 문자열 | Emacs 등 에디터 |