ITPE * JackerLab

SkipListMap

개요SkipListMap은 Skip List 자료구조를 기반으로 구현된 정렬된 Key-Value Map입니다. 트리 기반 구조(B-tree, AVL, Red-Black Tree)와 달리 난수 기반의 링크드 리스트 계층 구조를 활용하여, **검색, 삽입, 삭제 작업을 평균 O(log n)**의 성능으로 수행할 수 있으며, Java의 ConcurrentSkipListMap, Redis, RocksDB 등에서 활용됩니다.1. 개념 및 정의SkipListMap은 기본적으로 Skip List라는 자료구조를 기반으로 구성된 맵(Map)으로, Key를 기준으로 정렬된 상태를 유지하며, 중복되지 않는 키와 연관된 값을 저장합니다. Skip List는 여러 층의 연결 리스트를 사용하여 빠른 탐색을 가능하게 하는 구조이며..

개요LSM-Tree(Log-Structured Merge-Tree)는 디스크 기반 저장 장치에서 쓰기(write) 성능을 극대화하기 위해 설계된 트리 기반 자료구조입니다. RocksDB, LevelDB, Cassandra 등 다양한 NoSQL·NewSQL 시스템에서 채택되고 있으며, 로그 형태의 쓰기 버퍼와 다단계 정렬·병합(Merge) 구조를 활용하여 쓰기 집약형 워크로드에 특화된 성능을 제공합니다.1. 개념 및 정의 항목 설명 정의LSM-Tree는 메모리 상에 로그처럼 데이터를 기록한 후, 주기적으로 디스크에 정렬된 트리 형태로 병합하는 계층형 트리 아키텍처입니다.목적랜덤 쓰기를 순차 쓰기로 변환하여 디스크 I/O 병목을 해소함필요성기존 B-Tree 계열은 쓰기 성능 한계 및 디스크 IOPS 문제 ..

개요Skip List는 연결 리스트(linked list)에 다층 구조를 추가하여 이진 탐색 트리와 유사한 빠른 탐색, 삽입, 삭제를 지원하는 자료구조입니다. 평균적으로 O(log n) 시간 복잡도를 제공하며, 균형 유지가 복잡한 트리 구조 대신 간단한 구조로 고성능을 실현할 수 있어 데이터베이스, 인메모리 캐시 시스템 등 다양한 분야에서 활용됩니다.1. 개념 및 정의항목내용정의다층 연결 리스트를 사용하여 탐색 성능을 향상시키는 확률적(probabilistic) 자료구조목적이진 탐색 트리 수준의 탐색 속도 확보 및 구현 단순화필요성정렬된 데이터에서 빠른 검색, 삽입, 삭제를 지원하고 트리 리밸런싱 복잡성 감소Skip List는 간결한 구조와 높은 효율성으로 현대 시스템 설계에 널리 사용되고 있습니다.2...