ITPE * JackerLab

Concurrent Skip List

개요Concurrent Skip List는 Skip List 구조를 기반으로 한 동시성 정렬 자료구조로, 멀티스레드 환경에서 안전하고 빠르게 탐색, 삽입, 삭제를 수행할 수 있습니다. Java의 ConcurrentSkipListMap이나 C++의 ConcurrentSkipList 구현 등에서 활용되며, 트리 기반보다 구현이 간단하고 성능이 예측 가능한 것이 장점입니다.1. 개념 및 정의Concurrent Skip List는 Skip List의 계층적 링크 구조를 락-프리 또는 락-경량 방식으로 확장한 구조입니다. Skip List는 기본적으로 여러 레벨의 링크드 리스트를 중첩해 탐색 속도를 높이는 자료구조로, Concurrent 버전은 노드 삽입/삭제 시 다른 스레드와 충돌 없이 동작할 수 있도록 설계됩..

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는 여러 층의 연결 리스트를 사용하여 빠른 탐색을 가능하게 하는 구조이며..