[20250423] LSM Tree

import random

class Node:
    def __init__(self, key, value, level):
	self.key = key  # 노드의 고유 식별자 (정렬 기준)
	self.value = value  # 노드의 값
	self.forward = [None] * (level + 1)  # 각 레벨의 다음 노드 포인터 배열 (노드가 3층까지 있다면 0부터 3까지 포인터가 있음)

class SkipList:
    def __init__(self, max_level=16, p=0.5):
	self.max_level = max_level  # 최대 레벨, 기본값 16 (2^16 요소 예상)
	self.p = p  # 상위 레벨로 올라갈 확률
	self.level = 0  # 현재 최고 레벨
	self.header = Node(None, None, max_level)  # 모든 층의 시작점인 더미 노드, 단 하나만 존재.

    def random_level(self):
	"""새 노드의 레벨을 무작위로 결정"""
	level = 0
	# p=0.5 확율로 상위 레벨로 올라가기.
	while random.random() < self.p and level < self.max_level:
	    level += 1
	return level


    def _find_predecessors(self, key):
	"""각 레벨에서 목표 키 직전의 노드를 찾아 업데이트 배열을 반환."""
	# 업데이트 노드를 기록하기 위함?
	update = [None] * (self.max_level + 1)
	# 헤더 노드부터 시작
	current = self.header
	# 현재 레벨부터 0층까지 내려오면서 업데이트 노드를 기록
	# forward[i] 는 레벨 i 에서 
	# 첫 current.forward[i] 는 레벨 [i] 의 처음 노드를 가리킴.
	# 즉, 처음시작하면 level 3이라고 하면 current.forward[3] 은 레벨 3의 처음 노드를 가리킴.
	# 그리고 내부 루프가 끝나면 level 2로 가는거임
	# 직통 포인터는 뭘까? 만약에 내가 level 3에서 찾은 데이터가 있다면 그 녀석이 다음 current 가 된다
	# 여기서 forward만 2로 바꾸면 level 2에 존재하는 노드로 연결됨. 없을 수 있나? 아니 그럼 SkipList 의미가 없음
	# 각 상위층은 바로 밑 하위층에 무조건 있어야함. 그러므로 직통포인터가 있는셈이나 다름없음. 직접적으로 포인터가 연결되어 있지는 않지만!
	for i in range(self.level, -1, -1):  # self.level -1, -1 는 self.level 부터 0까지 -1로 줄어든다.
	    # 현재 노드가 목표 키보다 작으면 계속 이동
	    while current.forward[i] and current.forward[i].key < key:
		current = current.forward[i]
	    update[i] = current  # 업데이트 노드를 기록
	return update

    def search(self, key):
	"""키를 찾아 값을 반환. 없으면 None 반환"""
	# 키를 찾기 위한 업데이트 노드를 찾음
	update = self._find_predecessors(key)
	current = update[0].forward[0]
	# 0층에서 키를 찾으면 리턴        
	if current is not None and current.key == key:
	    return current.value
	return None

    def insert(self, key, value):
	"""키-값 쌍을 삽입하거나 기존 키의 값을 업데이트"""
	update = self._find_predecessors(key)
	current = update[0].forward[0]
	if current is not None and current.key == key:
	    current.value = value  # 키가 이미 있으면 값 업데이트
	else:
	    new_level = self.random_level()
	    if new_level > self.level:
		for i in range(self.level + 1, new_level + 1):
		    update[i] = self.header
		self.level = new_level
	    new_node = Node(key, value, new_level)
	    for i in range(new_level + 1):
		new_node.forward[i] = update[i].forward[i]
		update[i].forward[i] = new_node

    def delete(self, key):
	"""주어진 키를 삭제"""
	update = self._find_predecessors(key)
	current = update[0].forward[0]
	if current is not None and current.key == key:
	    for i in range(self.level + 1):
		if update[i].forward[i] != current:
		    break
		update[i].forward[i] = current.forward[i]
	    while self.level > 0 and self.header.forward[self.level] is None:
		self.level -= 1

    def __str__(self):
	"""스킵 리스트의 구조를 문자열로 반환"""
	result = []
	for lvl in range(self.level, -1, -1):
	    result.append(f"Level {lvl}:")
	    current = self.header.forward[lvl]
	    while current is not None:
		result.append(f" {current.key}")
		current = current.forward[lvl]
	    result.append("\n")
	return "".join(result)