# 插入节点 (Insert)
def insert(q, M, M_max):
L = get_random_level()
curr_node = entry_point
# 阶段1: 快速下潜 (Zoom-in)
for lc in range(L_max, L, -1):
curr_node = search_layer(q, curr_node, 1, lc)
# 阶段2: 逐层构建 (Construction)
for lc in range(min(L_max, L), -1, -1):
neighbors = search_layer(q, curr_node, ef, lc)
neighbors = select_neighbors(neighbors, M)
add_connections(q, neighbors, lc)
curr_node = q
if L > L_max: entry_point = q
# 搜索 (KNN Query)
def search_knn(q, K):
curr_node = entry_point
# 阶段1: 顶层下潜
for lc in range(L_max, 0, -1):
curr_node = search_layer(q, curr_node, 1, lc)
# 阶段2: 底层精搜
candidates = search_layer(q, curr_node, ef, 0)
return top_k(candidates, K)
# 贪心搜索细节 (search_layer)
def search_layer(q, entry, ef, lc):
candidates = [entry]
visited = {entry}
while candidates:
curr = get_closest(candidates, q)
if dist(curr, q) > dist(furthest, q): break
for nb in curr.neighbors[lc]:
if nb not in visited: candidates.add(nb)
return top_ef(candidates)