HNSW 算法详解

function search(query, k, efSearch):
    entry = graph.entryPoint
    current = entry

    for level from graph.maxLevel down to 1:
        changed = true
        while changed:
            changed = false
            for neighbor in current.neighbors[level]:
                if distance(query, neighbor) < distance(query, current):
                    current = neighbor
                    changed = true

    candidates = maxHeap()
    results = maxHeap()
    visited = set(current)

    push candidates with current
    push results with current

    while candidates is not empty:
        nearest = pop closest from candidates
        worst = farthest item in results

        if distance(query, nearest) > distance(query, worst):
            break

        for neighbor in nearest.neighbors[0]:
            if neighbor in visited:
                continue
            visited.add(neighbor)

            if results.size < efSearch
               or distance(query, neighbor) < distance(query, worst):
                push candidates with neighbor
                push results with neighbor
                keep only efSearch closest in results

    return top k closest from results

function insert(vector):
    newLevel = randomLevel()
    entry = graph.entryPoint
    current = entry

    for level from graph.maxLevel down to newLevel + 1:
        current = greedySearch(vector, current, level)

    for level from min(newLevel, graph.maxLevel) down to 0:
        pool = searchLayer(
            query = vector,
            entry = current,
            ef = efConstruction,
            level = level
        )

        neighbors = selectNeighbors(pool, M)
        connectBidirectional(vector, neighbors, level)

        for neighbor in neighbors:
            if neighbor.degree(level) > M:
                neighbor.neighbors[level] =
                    selectNeighbors(neighbor.neighbors[level], M)

        current = closest item in pool

    if newLevel > graph.maxLevel:
        graph.entryPoint = vector
        graph.maxLevel = newLevel