motedb 0.1.4

//! FreshDiskANN Index - 统一索引接口

use crate::error::Result;
use crate::types::RowId;
use crate::distance::DistanceKind;
use std::path::PathBuf;
use std::collections::HashMap;
use super::{
    FreshVamanaGraph, FreshGraphConfig,
    VamanaSSTFile, Candidate, VectorNode,
    MultiLevelSearch, CompactionStrategy, CompactionTrigger,
};

/// FreshDiskANN 配置
#[derive(Debug, Clone)]
pub struct FreshDiskANNConfig {
    /// Fresh Graph 配置
    pub fresh_config: FreshGraphConfig,
    
    /// Compaction 触发器
    pub compaction_trigger: CompactionTrigger,
    
    /// 数据库目录
    pub data_dir: PathBuf,
}

impl Default for FreshDiskANNConfig {
    fn default() -> Self {
        Self {
            fresh_config: FreshGraphConfig::default(),
            compaction_trigger: CompactionTrigger::default(),
            data_dir: PathBuf::from("."),
        }
    }
}

/// FreshDiskANN 索引
pub struct FreshDiskANNIndex {
    /// Level 0: Fresh Graph
    fresh_graph: FreshVamanaGraph,
    
    /// Level 1: SST Files
    level1_ssts: Vec<VamanaSSTFile>,
    
    /// Level 2+: Merged Index
    merged_index: Option<VamanaSSTFile>,
    
    /// 配置
    config: FreshDiskANNConfig,
    
    /// 距离度量
    metric: DistanceKind,
    
    /// 多层搜索器
    multi_level: MultiLevelSearch,
    
    /// Compaction 策略
    compaction: CompactionStrategy,
}

impl FreshDiskANNIndex {
    /// 创建新索引
    pub fn create(config: FreshDiskANNConfig, metric: DistanceKind) -> Result<Self> {
        let fresh_graph = FreshVamanaGraph::new(config.fresh_config.clone(), metric);
        let multi_level = MultiLevelSearch::new();
        let compaction = CompactionStrategy::new(config.compaction_trigger.clone());
        
        Ok(Self {
            fresh_graph,
            level1_ssts: Vec::new(),
            merged_index: None,
            config,
            metric,
            multi_level,
            compaction,
        })
    }
    
    /// 插入向量
    pub fn insert(&mut self, id: RowId, vector: Vec<f32>) -> Result<()> {
        // 插入到 Fresh Graph
        self.fresh_graph.insert(id, vector)?;
        
        // 检查是否需要 flush
        if self.fresh_graph.should_flush() {
            self.flush_fresh_graph()?;
        }
        
        Ok(())
    }
    
    /// 🚀 批量插入向量（高性能）
    /// 
    /// **核心优化**：延迟图构建，避免逐个插入的锁竞争
    pub fn batch_insert(&mut self, vectors: &[(RowId, Vec<f32>)]) -> Result<()> {
        if vectors.is_empty() {
            return Ok(());
        }
        
        // 批量插入到 Fresh Graph
        self.fresh_graph.batch_insert(vectors)?;
        
        // 检查是否需要 flush
        if self.fresh_graph.should_flush() {
            self.flush_fresh_graph()?;
        }
        
        Ok(())
    }
    
    /// 查询（多层合并）
    pub fn search(&self, query: &[f32], k: usize, ef: usize) -> Result<Vec<Candidate>> {
        // Scale ef based on k for better recall
        let ef = if k <= 10 {
            ef.max(k * 3).max(80)
        } else if k <= 30 {
            ef.max(k * 3).max(100)
        } else {
            ef.max(k * 3).max(120)
        };

        // Scale expanded_k dynamically based on dataset size:
        // - Small (<1K vectors): k*3, cap 200
        // - Medium (1K-100K): k*5, cap 500
        // - Large (>100K): k*10, cap 2000
        let total_vectors = self.fresh_graph.node_count()
            + self.level1_ssts.iter().map(|s| s.active_node_count()).sum::<usize>()
            + self.merged_index.as_ref().map(|m| m.active_node_count()).unwrap_or(0);

        let expanded_k = if total_vectors < 1_000 {
            (k * 3).max(k + 30).min(200)
        } else if total_vectors < 100_000 {
            (k * 5).max(k + 50).min(500)
        } else {
            (k * 10).max(k + 100).min(2000)
        };
        
        // 1. 查询 Fresh Graph
        let fresh_results = if !self.fresh_graph.is_empty() {
            self.fresh_graph.search(query, expanded_k, ef)?
        } else {
            Vec::new()
        };
        
        // 2. 查询每个 L1 SST（扩展 k）
        let mut all_l1_results = Vec::new();
        for sst in &self.level1_ssts {
            let sst_results = sst.search(query, expanded_k, ef)?;
            all_l1_results.extend(sst_results);
        }
        
        // 3. 查询 L2 merged index（扩展 k）
        let l2_results = if let Some(ref merged) = self.merged_index {
            merged.search(query, expanded_k, ef)?
        } else {
            Vec::new()
        };
        
        // 4. 合并并去重
        let merged = self.multi_level.merge(
            fresh_results,
            all_l1_results,
            l2_results,
            k,
        )?;
        
        Ok(merged)
    }
    
    /// Flush Fresh Graph 到 SST
    fn flush_fresh_graph(&mut self) -> Result<()> {
        println!("[FreshDiskANN] Flushing Fresh Graph to L1 SST...");
        
        // 1. 导出 Fresh Graph 的所有节点
        let nodes = self.fresh_graph.export_nodes()?;
        let medoid = self.fresh_graph.medoid();
        
        if nodes.is_empty() {
            println!("[FreshDiskANN] Fresh Graph is empty, skip flush");
            return Ok(());
        }
        
        // 2. 生成 SST 文件名
        let l1_index = self.level1_ssts.len();
        let sst_path = self.config.data_dir.join(format!("l1_{:06}.sst", l1_index));
        
        // 3. 创建 SST 文件
        let sst_file = VamanaSSTFile::create(&sst_path, nodes, medoid)?;
        
        println!(
            "[FreshDiskANN] Created L1 SST: {:?}, {} nodes",
            sst_path,
            sst_file.metadata().node_count
        );
        
        // 4. 添加到 Level 1
        self.level1_ssts.push(sst_file);
        
        // 5. 清空 Fresh Graph
        self.fresh_graph.clear()?;
        
        // 6. 检查是否需要 compaction
        if self.compaction.should_compact(&self.level1_ssts) {
            self.compact_l1_to_l2()?;
        }
        
        Ok(())
    }
    
    /// Compaction: L1 → L2 (真正的图合并 + 图重建)
    fn compact_l1_to_l2(&mut self) -> Result<()> {
        println!("[FreshDiskANN] Compacting {} L1 SSTs to L2...", self.level1_ssts.len());
        
        if self.level1_ssts.is_empty() {
            return Ok(());
        }
        
        // 🚀 Phase 5: 真正的图合并 Compaction
        
        // 1. 收集所有 L1 SST 的节点（过滤已删除节点）
        let mut all_nodes = Vec::new();
        let mut total_before = 0usize;
        let mut active_after = 0usize;
        
        for sst in &self.level1_ssts {
            let node_count = sst.metadata().node_count as usize;
            total_before += node_count;
            
            let nodes = sst.export_active_nodes()?;
            active_after += nodes.len();
            all_nodes.extend(nodes);
        }
        
        // 2. 如果有 L2 index，也合并进来
        if let Some(ref l2_sst) = self.merged_index {
            let l2_nodes = l2_sst.export_active_nodes()?;
            total_before += l2_sst.metadata().node_count as usize;
            active_after += l2_nodes.len();
            all_nodes.extend(l2_nodes);
        }
        
        println!(
            "[FreshDiskANN] Compaction: collected {} active nodes (removed {} tombstones)",
            active_after,
            total_before - active_after
        );
        
        if all_nodes.is_empty() {
            println!("[FreshDiskANN] No active nodes after compaction, skip");
            return Ok(());
        }
        
        // 3. 去重（保留最新的节点）
        use std::collections::HashMap;
        let mut dedup_map: HashMap<RowId, VectorNode> = HashMap::new();
        for (row_id, node) in all_nodes {
            // 简单策略：后来的覆盖之前的（假设 timestamp 更新）
            dedup_map.insert(row_id, node);
        }
        
        let merged_nodes: Vec<_> = dedup_map.into_iter().collect();
        println!("[FreshDiskANN] After dedup: {} unique nodes", merged_nodes.len());
        
        // 🚀 Phase 9: 选择多个锚点（用于图重建的起始点）
        // 🎯 平衡优化：使用8个锚点（平衡性能与质量）
        let num_anchors = 8.min(merged_nodes.len()); // 8个锚点
        let anchor_points = self.select_anchor_points(&merged_nodes, num_anchors)?;
        let primary_medoid = anchor_points[0]; // 第一个锚点作为主 medoid
        
        println!("[FreshDiskANN] Selected {} anchor points, primary medoid: {}", 
            anchor_points.len(), primary_medoid);
        println!("  Anchor points: {:?}", anchor_points);
        
        // 🚀 Phase 9: 图重建（使用 Vamana 算法 + 多锚点搜索）
        println!("[FreshDiskANN] Phase 9: Rebuilding graph with multi-anchor Vamana (conservative)...");
        let rebuild_start = std::time::Instant::now();
        // 🔥 先用主 medoid 构建基础图，然后再优化
        let rebuilt_nodes = self.rebuild_graph_with_medoid_fallback(merged_nodes, primary_medoid, &anchor_points)?;
        println!(
            "[FreshDiskANN] Graph rebuild completed in {:.2?}",
            rebuild_start.elapsed()
        );
        
        // 5. 创建新的 L2 SST
        let l2_path = self.config.data_dir.join("l2_merged.sst");
        
        // 删除旧的 L2 文件（如果存在）
        if l2_path.exists() {
            std::fs::remove_file(&l2_path)?;
        }
        
        let new_l2 = VamanaSSTFile::create(&l2_path, rebuilt_nodes, primary_medoid)?;
        
        println!(
            "[FreshDiskANN] L2 merged index created: {:?}, {} nodes",
            l2_path,
            new_l2.metadata().node_count
        );
        
        // 6. 删除旧的 L1 SSTs
        for sst in self.level1_ssts.drain(..) {
            let path = sst.path().to_path_buf();
            drop(sst);
            if let Err(e) = std::fs::remove_file(&path) {
                eprintln!("[FreshDiskANN] Failed to remove L1 SST {:?}: {}", path, e);
            }
        }
        
        // 7. 更新 L2 index
        self.merged_index = Some(new_l2);
        
        println!("[FreshDiskANN] Compaction complete");
        Ok(())
    }
    
    /// Phase 9/10: 使用 Vamana 算法重建图（多锚点搜索 + medoid fallback）
    fn rebuild_graph_with_medoid_fallback(&self, nodes: Vec<(RowId, VectorNode)>, medoid: RowId, anchor_points: &[RowId]) -> Result<Vec<(RowId, VectorNode)>> {
        // 🔥 根据配置决定使用 Phase 9 (max_degree=64) 还是 Phase 10 (max_degree=128)
        let max_degree = self.config.fresh_config.max_degree;
        let search_list_size = self.config.fresh_config.search_list_size;
        let node_count = nodes.len();
        
        let phase = if max_degree >= 100 && search_list_size >= 500 {
            "Phase 10"
        } else {
            "Phase 9"
        };
        
        println!("[FreshDiskANN] {}: Graph rebuild (max_degree={}, search_list={})",
            phase, max_degree, search_list_size);
        
        // 1. 创建 id -> index 映射
        use std::collections::HashMap;
        let mut id_to_idx: HashMap<RowId, usize> = HashMap::new();
        for (idx, (id, _)) in nodes.iter().enumerate() {
            id_to_idx.insert(*id, idx);
        }
        
        let _medoid_idx = *id_to_idx.get(&medoid).ok_or_else(|| {
            crate::error::StorageError::InvalidData("Medoid not found".into())
        })?;
        
        // 转换 anchor_points 为 indices
        let anchor_indices: Vec<usize> = anchor_points.iter()
            .filter_map(|&id| id_to_idx.get(&id).copied())
            .collect();
        
        // 2. 初始化所有节点的邻居为空
        let mut graph: Vec<Vec<RowId>> = vec![Vec::new(); node_count];
        
        // 🔥 Phase 9: Bootstrap Phase - 随机初始化图（必须！）
        println!("[FreshDiskANN] Phase 9: Bootstrap - Random initialization...");
        let bootstrap_neighbors = 20; // 增加到 20 个邻居
        
        use rand::Rng;
        let mut rng = rand::thread_rng();
        
        for i in 0..node_count {
            // 随机选择 bootstrap_neighbors 个邻居
            let mut random_neighbors = Vec::new();
            for _ in 0..bootstrap_neighbors.min(node_count - 1) {
                let random_idx = rng.gen_range(0..node_count);
                if random_idx != i {
                    random_neighbors.push(nodes[random_idx].0);
                }
            }
            
            // 去重
            random_neighbors.sort();
            random_neighbors.dedup();
            
            graph[i] = random_neighbors;
        }
        
        let bootstrap_avg_degree: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        println!("  Bootstrap complete: avg degree = {:.2}", bootstrap_avg_degree);
        
        // 3. Round 1 - 使用多锚点搜索构建基础图
        println!("[FreshDiskANN] Round 1: Building base graph with top-k...");
        
        for (i, (id, node)) in nodes.iter().enumerate() {
            if (i + 1) % 1000 == 0 {
                println!("  Round 1: {} / {} nodes...", i + 1, node_count);
            }
            
            // 从多个锚点并行搜索
            let candidates = self.multi_anchor_greedy_search(
                &node.vector,
                &nodes,
                &graph,
                &id_to_idx,
                search_list_size,
                *id,
                &anchor_indices,
            )?;
            
            // Round 1: 直接取 top-k（不使用 RobustPrune）
            let mut candidates_sorted = candidates;
            candidates_sorted.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
            let pruned_neighbors: Vec<RowId> = candidates_sorted
                .into_iter()
                .take(max_degree)
                .map(|(id, _)| id)
                .collect();
            
            graph[i] = pruned_neighbors;
        }
        
        let avg_degree_round1: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        println!("  Round 1 complete: avg degree = {:.2}", avg_degree_round1);
        
        // 4. Round 2 - RobustPrune 优化（仅在 Phase 10 模式）
        if max_degree >= 100 && search_list_size >= 500 {
            println!("[FreshDiskANN] Round 2: RobustPrune optimization...");
            
            for (i, (id, node)) in nodes.iter().enumerate() {
                if (i + 1) % 1000 == 0 {
                    println!("  Round 2: {} / {} nodes...", i + 1, node_count);
                }
                
                let candidates = self.multi_anchor_greedy_search(
                    &node.vector,
                    &nodes,
                    &graph,
                    &id_to_idx,
                    search_list_size,
                    *id,
                    &anchor_indices,
                )?;
                
                // Round 2: RobustPrune
                let pruned_neighbors = self.robust_prune(
                    &node.vector,
                    candidates,
                    max_degree,
                    1.2,
                    &nodes,
                    &id_to_idx,
                )?;
                
                graph[i] = pruned_neighbors.clone();
                
                // 双向连接维护
                for &neighbor_id in &pruned_neighbors {
                    if let Some(&neighbor_idx) = id_to_idx.get(&neighbor_id) {
                        if graph[neighbor_idx].len() < max_degree && !graph[neighbor_idx].contains(id) {
                            graph[neighbor_idx].push(*id);
                        } else if graph[neighbor_idx].len() >= max_degree {
                            let neighbor_node = &nodes[neighbor_idx];
                            let mut new_candidates: Vec<(RowId, f32)> = graph[neighbor_idx]
                                .iter()
                                .map(|&nid| {
                                    let nidx = id_to_idx[&nid];
                                    let dist = self.compute_distance(&neighbor_node.1.vector, &nodes[nidx].1.vector);
                                    (nid, dist)
                                })
                                .collect();
                            
                            let dist_to_current = self.compute_distance(&neighbor_node.1.vector, &node.vector);
                            new_candidates.push((*id, dist_to_current));
                            
                            let updated_neighbors = self.robust_prune(
                                &neighbor_node.1.vector,
                                new_candidates,
                                max_degree,
                                1.2,
                                &nodes,
                                &id_to_idx,
                            )?;
                            
                            graph[neighbor_idx] = updated_neighbors;
                        }
                    }
                }
            }
            
            let avg_degree_round2: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
            println!("  Round 2 complete: avg degree = {:.2}", avg_degree_round2);
        }
        
        // 5. 最终统计
        let empty_neighbors = graph.iter().filter(|g| g.is_empty()).count();
        let avg_degree_final: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        println!("  Final graph: avg degree = {:.2}, empty = {}", avg_degree_final, empty_neighbors);
        
        // 6. 将图转换回节点列表
        let mut rebuilt_nodes = Vec::with_capacity(node_count);
        for (i, (id, node)) in nodes.into_iter().enumerate() {
            let mut updated_node = node;
            updated_node.neighbors = graph[i].clone();
            rebuilt_nodes.push((id, updated_node));
        }
        
        println!("[FreshDiskANN] Graph rebuild complete!");
        Ok(rebuilt_nodes)
    }
    
    /// Phase 9: 使用 Vamana 算法重建图（多锚点搜索）- 备用方案
    #[allow(dead_code)]
    fn rebuild_graph_with_anchors(&self, nodes: Vec<(RowId, VectorNode)>, anchor_points: Vec<RowId>) -> Result<Vec<(RowId, VectorNode)>> {
        // 🔥 Phase 9: 增大 max_degree
        let max_degree = 64; // 从 32 增大到 64
        let node_count = nodes.len();
        
        println!(
            "[FreshDiskANN] Phase 9: Rebuilding graph with multi-anchor Vamana...",
        );
        println!(
            "  Nodes: {}, Max Degree: {} (increased from 32), Anchors: {}",
            node_count, max_degree, anchor_points.len()
        );
        
        // 1. 创建 id -> index 映射
        use std::collections::HashMap;
        let mut id_to_idx: HashMap<RowId, usize> = HashMap::new();
        for (idx, (id, _)) in nodes.iter().enumerate() {
            id_to_idx.insert(*id, idx);
        }
        
        // 转换 anchor_points 为 indices
        let anchor_indices: Vec<usize> = anchor_points.iter()
            .filter_map(|&id| id_to_idx.get(&id).copied())
            .collect();
        
        if anchor_indices.is_empty() {
            return Err(crate::error::StorageError::InvalidData("No valid anchor points".into()));
        }
        
        println!("  Using {} anchor indices: {:?}", anchor_indices.len(), &anchor_indices[..anchor_indices.len().min(5)]);
        
        // 2. 初始化所有节点的邻居为空
        let mut graph: Vec<Vec<RowId>> = vec![Vec::new(); node_count];
        
        // 🔥 Phase 9: Bootstrap Phase - 随机初始化图（必须！）
        println!("[FreshDiskANN] Phase 9: Bootstrap - Random initialization...");
        let bootstrap_neighbors = 20; // 增加到 20 个邻居
        
        use rand::Rng;
        let mut rng = rand::thread_rng();
        
        for i in 0..node_count {
            // 随机选择 bootstrap_neighbors 个邻居
            let mut random_neighbors = Vec::new();
            for _ in 0..bootstrap_neighbors.min(node_count - 1) {
                let random_idx = rng.gen_range(0..node_count);
                if random_idx != i {
                    random_neighbors.push(nodes[random_idx].0);
                }
            }
            
            // 去重
            random_neighbors.sort();
            random_neighbors.dedup();
            
            graph[i] = random_neighbors;
        }
        
        let bootstrap_avg_degree: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        println!("  Bootstrap complete: avg degree = {:.2}", bootstrap_avg_degree);
        
        // 3. 使用 Vamana 算法为每个节点构建邻居（第一轮优化）
        println!("[FreshDiskANN] Phase 9: Round 1 - Multi-anchor Vamana optimization...");
        let search_list_size = (max_degree as f32 * 2.0) as usize; // 增大到 2.0 × R
        
        for (i, (id, node)) in nodes.iter().enumerate() {
            if (i + 1) % 1000 == 0 {
                println!("  Round 1: {} / {} nodes...", i + 1, node_count);
            }
            
            // 🔥 Phase 9 关键：从多个锚点并行搜索，然后合并结果
            let candidates = self.multi_anchor_greedy_search(
                &node.vector,
                &nodes,
                &graph,
                &id_to_idx,
                search_list_size,
                *id,
                &anchor_indices,
            )?;
            
            let candidates_count2 = candidates.len();
            
            // 🔥 使用 RobustPrune 选择多样性邻居（Phase 9: 增大 alpha）
            let pruned_neighbors = self.robust_prune(
                &node.vector,
                candidates,
                max_degree,
                2.5, // 🔥 Phase 9: 增大 alpha 从 1.2 到 2.5（降低剪枝强度）
                &nodes,
                &id_to_idx,
            )?;
            
            // 调试：检查剪枝结果
            if i < 5 {
                println!("  Node {} candidates: {}, pruned: {}", i, candidates_count2, pruned_neighbors.len());
            }
            
            graph[i] = pruned_neighbors.clone();
            
            // 🔥 Phase 7: 双向连接（反向边维护）
            for &neighbor_id in &pruned_neighbors {
                if let Some(&neighbor_idx) = id_to_idx.get(&neighbor_id) {
                    // 如果邻居的度数未满，添加反向边
                    if graph[neighbor_idx].len() < max_degree && !graph[neighbor_idx].contains(id) {
                        graph[neighbor_idx].push(*id);
                    } else if graph[neighbor_idx].len() >= max_degree {
                        // 如果邻居的度数已满，使用 RobustPrune 更新
                        let neighbor_node = &nodes[neighbor_idx];
                        let mut new_candidates: Vec<(RowId, f32)> = graph[neighbor_idx]
                            .iter()
                            .map(|&nid| {
                                let nidx = id_to_idx[&nid];
                                let dist = self.compute_distance(&neighbor_node.1.vector, &nodes[nidx].1.vector);
                                (nid, dist)
                            })
                            .collect();
                        
                        // 添加当前节点作为候选
                        let dist_to_current = self.compute_distance(&neighbor_node.1.vector, &node.vector);
                        new_candidates.push((*id, dist_to_current));
                        
                        // 重新 prune
                        let updated_neighbors = self.robust_prune(
                            &neighbor_node.1.vector,
                            new_candidates,
                            max_degree,
                            1.2,
                            &nodes,
                            &id_to_idx,
                        )?;
                        
                        graph[neighbor_idx] = updated_neighbors;
                    }
                }
            }
        }
        
        println!("[FreshDiskANN] Round 1 complete!");
        
        // 4. 将图转换回节点列表
        let mut rebuilt_nodes = Vec::with_capacity(node_count);
        for (i, (id, node)) in nodes.into_iter().enumerate() {
            let mut updated_node = node;
            updated_node.neighbors = graph[i].clone();
            rebuilt_nodes.push((id, updated_node));
        }
        
        println!("[FreshDiskANN] Vamana graph rebuild complete!");
        Ok(rebuilt_nodes)
    }
    
    /// Phase 9: 多锚点贪心搜索（从多个起点并行搜索，合并结果）
    fn multi_anchor_greedy_search(
        &self,
        query: &[f32],
        nodes: &[(RowId, VectorNode)],
        graph: &[Vec<RowId>],
        id_to_idx: &HashMap<RowId, usize>,
        search_list_size: usize,
        exclude_id: RowId,
        anchor_indices: &[usize],
    ) -> Result<Vec<(RowId, f32)>> {
        use std::collections::{BinaryHeap, HashSet};
        use std::cmp::Ordering;
        
        // 最小堆（距离小的优先）
        #[derive(Clone)]
        struct SearchCandidate {
            id: RowId,
            distance: f32,
        }
        
        impl PartialEq for SearchCandidate {
            fn eq(&self, other: &Self) -> bool {
                self.distance == other.distance
            }
        }
        
        impl Eq for SearchCandidate {}
        
        impl PartialOrd for SearchCandidate {
            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                // 反转比较，实现最小堆
                other.distance.partial_cmp(&self.distance)
            }
        }
        
        impl Ord for SearchCandidate {
            fn cmp(&self, other: &Self) -> Ordering {
                self.partial_cmp(other).unwrap_or(Ordering::Equal)
            }
        }
        
        // 🔥 Phase 9: 从所有锚点开始搜索
        let mut visited = HashSet::new();
        let mut candidates = BinaryHeap::new();
        
        // 初始化：将所有锚点加入候选队列
        for &anchor_idx in anchor_indices {
            let anchor_id = nodes[anchor_idx].0;
            let dist = self.compute_distance(query, &nodes[anchor_idx].1.vector);
            
            candidates.push(SearchCandidate {
                id: anchor_id,
                distance: dist,
            });
            visited.insert(anchor_id);
        }
        
        let mut result = Vec::new();
        
        // 标准 Vamana 贪心搜索
        while let Some(current) = candidates.pop() {
            if current.id != exclude_id {
                result.push((current.id, current.distance));
            }
            
            if result.len() >= search_list_size {
                break;
            }
            
            // 扩展邻居
            if let Some(&current_idx) = id_to_idx.get(&current.id) {
                for &neighbor_id in &graph[current_idx] {
                    if visited.contains(&neighbor_id) {
                        continue;
                    }
                    visited.insert(neighbor_id);
                    
                    if let Some(&neighbor_idx) = id_to_idx.get(&neighbor_id) {
                        let dist = self.compute_distance(query, &nodes[neighbor_idx].1.vector);
                        candidates.push(SearchCandidate {
                            id: neighbor_id,
                            distance: dist,
                        });
                    }
                }
            }
        }
        
        // 如果结果不够，使用暴力搜索补充（限制为 2 × search_list_size）
        if result.len() < search_list_size {
            let max_brute_force = (search_list_size * 2).min(nodes.len());
            
            // 🔥 Phase 9 修复：采样补充（而非全量扫描）
            let step = if nodes.len() > max_brute_force {
                nodes.len() / max_brute_force
            } else {
                1
            };
            
            for (_idx, (id, node)) in nodes.iter().enumerate().step_by(step) {
                if *id == exclude_id || visited.contains(id) {
                    continue;
                }
                
                let dist = self.compute_distance(query, &node.vector);
                result.push((*id, dist));
                visited.insert(*id);
                
                if result.len() >= max_brute_force {
                    break;
                }
            }
        }
        
        // 排序并返回
        result.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
        result.truncate(search_list_size);
        
        Ok(result)
    }
    
    /// Phase 7: Vamana 贪心搜索（用于构建邻居）- 保留用于向后兼容
    #[allow(dead_code)]
    fn vamana_greedy_search(
        &self,
        query: &[f32],
        nodes: &[(RowId, VectorNode)],
        graph: &[Vec<RowId>],
        id_to_idx: &HashMap<RowId, usize>,
        search_list_size: usize,
        exclude_id: RowId,
        medoid_idx: usize,
    ) -> Result<Vec<(RowId, f32)>> {
        use std::collections::BinaryHeap;
        use std::cmp::Ordering;
        
        // 最小堆（距离小的优先）
        #[derive(Clone)]
        struct SearchCandidate {
            id: RowId,
            distance: f32,
        }
        
        impl PartialEq for SearchCandidate {
            fn eq(&self, other: &Self) -> bool {
                self.distance == other.distance
            }
        }
        
        impl Eq for SearchCandidate {}
        
        impl PartialOrd for SearchCandidate {
            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                // 反转比较，实现最小堆
                other.distance.partial_cmp(&self.distance)
            }
        }
        
        impl Ord for SearchCandidate {
            fn cmp(&self, other: &Self) -> Ordering {
                self.partial_cmp(other).unwrap_or(Ordering::Equal)
            }
        }
        
        // 🔥 Phase 7: 使用 medoid 作为起始点
        let start_id = nodes[medoid_idx].0;
        let start_dist = self.compute_distance(query, &nodes[medoid_idx].1.vector);
        
        let mut visited = std::collections::HashSet::new();
        let mut candidates = BinaryHeap::new();
        
        candidates.push(SearchCandidate {
            id: start_id,
            distance: start_dist,
        });
        visited.insert(start_id);
        
        let mut result = Vec::new();
        
        while let Some(current) = candidates.pop() {
            if current.id != exclude_id {
                result.push((current.id, current.distance));
            }
            
            if result.len() >= search_list_size {
                break;
            }
            
            // 扩展邻居
            if let Some(&current_idx) = id_to_idx.get(&current.id) {
                for &neighbor_id in &graph[current_idx] {
                    if visited.contains(&neighbor_id) {
                        continue;
                    }
                    visited.insert(neighbor_id);
                    
                    if let Some(&neighbor_idx) = id_to_idx.get(&neighbor_id) {
                        let dist = self.compute_distance(query, &nodes[neighbor_idx].1.vector);
                        candidates.push(SearchCandidate {
                            id: neighbor_id,
                            distance: dist,
                        });
                    }
                }
            }
        }
        
        // 如果结果不够，使用随机节点补充
        if result.len() < search_list_size {
            for (id, node) in nodes.iter() {
                if *id == exclude_id || visited.contains(id) {
                    continue;
                }
                
                let dist = self.compute_distance(query, &node.vector);
                result.push((*id, dist));
                
                if result.len() >= search_list_size {
                    break;
                }
            }
        }
        
        // 排序并返回
        result.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
        result.truncate(search_list_size);
        
        Ok(result)
    }
    
    /// Phase 7: RobustPrune 算法（多样性邻居选择）
    fn robust_prune(
        &self,
        _query: &[f32],
        mut candidates: Vec<(RowId, f32)>,
        max_degree: usize,
        alpha: f32, // 多样性参数
        nodes: &[(RowId, VectorNode)],
        id_to_idx: &HashMap<RowId, usize>,
    ) -> Result<Vec<RowId>> {
        // 按距离排序
        candidates.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
        
        let mut result = Vec::new();
        
        for (candidate_id, candidate_dist) in candidates {
            if result.len() >= max_degree {
                break;
            }
            
            // 🔥 关键：RobustPrune 多样性检查
            let mut should_add = true;
            
            if let Some(&candidate_idx) = id_to_idx.get(&candidate_id) {
                let candidate_vec = &nodes[candidate_idx].1.vector;
                
                for &existing_id in &result {
                    if let Some(&existing_idx) = id_to_idx.get(&existing_id) {
                        let existing_vec = &nodes[existing_idx].1.vector;
                        let dist_to_existing = self.compute_distance(candidate_vec, existing_vec);
                        
                        // 如果候选节点到已选节点的距离 < alpha × 到查询点的距离，则跳过
                        if dist_to_existing < alpha * candidate_dist {
                            should_add = false;
                            break;
                        }
                    }
                }
                
                if should_add {
                    result.push(candidate_id);
                }
            }
        }
        
        Ok(result)
    }
    
    /// Phase 10: 两轮图优化（增大参数 + RobustPrune）
    #[allow(dead_code)]
    fn rebuild_graph_phase10(&self, nodes: Vec<(RowId, VectorNode)>, _medoid: RowId, anchor_points: &[RowId]) -> Result<Vec<(RowId, VectorNode)>> {
        // 🔥 Phase 10: 增大 max_degree 到 128
        let max_degree = 128;
        let search_list_size = 1000; // 增大到 1000
        let node_count = nodes.len();
        
        println!("[FreshDiskANN] Phase 10: Two-round graph optimization...");
        println!("  Nodes: {}, Max Degree: 128, Search List: 1000, Anchors: {}", 
            node_count, anchor_points.len());
        
        // 1. 创建 id -> index 映射
        use std::collections::HashMap;
        let mut id_to_idx: HashMap<RowId, usize> = HashMap::new();
        for (idx, (id, _)) in nodes.iter().enumerate() {
            id_to_idx.insert(*id, idx);
        }
        
        let anchor_indices: Vec<usize> = anchor_points.iter()
            .filter_map(|&id| id_to_idx.get(&id).copied())
            .collect();
        
        // 2. Bootstrap - 随机初始化图
        let mut graph: Vec<Vec<RowId>> = vec![Vec::new(); node_count];
        
        println!("[FreshDiskANN] Phase 10: Bootstrap initialization...");
        let bootstrap_neighbors = 30; // 增加到 30
        
        use rand::Rng;
        let mut rng = rand::thread_rng();
        
        for i in 0..node_count {
            let mut random_neighbors = Vec::new();
            for _ in 0..bootstrap_neighbors.min(node_count - 1) {
                let random_idx = rng.gen_range(0..node_count);
                if random_idx != i {
                    random_neighbors.push(nodes[random_idx].0);
                }
            }
            random_neighbors.sort();
            random_neighbors.dedup();
            graph[i] = random_neighbors;
        }
        
        let bootstrap_avg_degree: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        println!("  Bootstrap complete: avg degree = {:.2}", bootstrap_avg_degree);
        
        // 3. Round 1 - 直接取 top-k
        println!("[FreshDiskANN] Phase 10 Round 1: Building base graph...");
        
        for (i, (id, node)) in nodes.iter().enumerate() {
            if (i + 1) % 1000 == 0 {
                println!("  Round 1: {} / {} nodes...", i + 1, node_count);
            }
            
            let candidates = self.multi_anchor_greedy_search(
                &node.vector,
                &nodes,
                &graph,
                &id_to_idx,
                search_list_size,
                *id,
                &anchor_indices,
            )?;
            
            // Round 1: 直接取 top-k
            let mut candidates_sorted = candidates;
            candidates_sorted.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
            let pruned_neighbors: Vec<RowId> = candidates_sorted
                .into_iter()
                .take(max_degree)
                .map(|(id, _)| id)
                .collect();
            
            graph[i] = pruned_neighbors;
        }
        
        let avg_degree_round1: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        println!("  Round 1 complete: avg degree = {:.2}", avg_degree_round1);
        
        // 4. Round 2 - RobustPrune 优化
        println!("[FreshDiskANN] Phase 10 Round 2: RobustPrune optimization...");
        
        for (i, (id, node)) in nodes.iter().enumerate() {
            if (i + 1) % 1000 == 0 {
                println!("  Round 2: {} / {} nodes...", i + 1, node_count);
            }
            
            let candidates = self.multi_anchor_greedy_search(
                &node.vector,
                &nodes,
                &graph,
                &id_to_idx,
                search_list_size,
                *id,
                &anchor_indices,
            )?;
            
            // Round 2: RobustPrune
            let pruned_neighbors = self.robust_prune(
                &node.vector,
                candidates,
                max_degree,
                1.2,
                &nodes,
                &id_to_idx,
            )?;
            
            graph[i] = pruned_neighbors;
        }
        
        let avg_degree_final: f32 = graph.iter().map(|g| g.len()).sum::<usize>() as f32 / node_count as f32;
        let empty_neighbors = graph.iter().filter(|g| g.is_empty()).count();
        println!("  Round 2 complete: avg degree = {:.2}, empty = {}", avg_degree_final, empty_neighbors);
        
        // 5. 将图转换回节点列表
        let mut rebuilt_nodes = Vec::with_capacity(node_count);
        for (i, (id, node)) in nodes.into_iter().enumerate() {
            let mut updated_node = node;
            updated_node.neighbors = graph[i].clone();
            rebuilt_nodes.push((id, updated_node));
        }
        
        println!("[FreshDiskANN] Phase 10 graph rebuild complete!");
        Ok(rebuilt_nodes)
    }
    
    /// Phase 9: 使用 K-Means 选择多个锚点（替代单一 medoid）
    fn select_anchor_points(&self, nodes: &[(RowId, VectorNode)], k: usize) -> Result<Vec<RowId>> {
        if nodes.is_empty() {
            return Err(crate::error::StorageError::InvalidData("No nodes to select anchors".into()));
        }
        
        let k = k.min(nodes.len());
        
        println!("[FreshDiskANN] Phase 9: Selecting {} anchor points using K-Means...", k);
        
        // 🔥 K-Means 聚类
        let dim = nodes[0].1.vector.len();
        
        // 1. 随机初始化 k 个中心点
        use rand::seq::SliceRandom;
        let mut rng = rand::thread_rng();
        
        let mut centers: Vec<Vec<f32>> = nodes
            .choose_multiple(&mut rng, k)
            .map(|(_, node)| node.vector.clone())
            .collect();
        
        // 2. K-Means 迭代（最多 10 轮）
        let max_iterations = 10;
        for iter in 0..max_iterations {
            // 分配每个节点到最近的簇
            let mut clusters: Vec<Vec<usize>> = vec![Vec::new(); k];
            
            for (idx, (_, node)) in nodes.iter().enumerate() {
                let mut min_dist = f32::MAX;
                let mut best_cluster = 0;
                
                for (c_idx, center) in centers.iter().enumerate() {
                    let dist = self.compute_distance(&node.vector, center);
                    if dist < min_dist {
                        min_dist = dist;
                        best_cluster = c_idx;
                    }
                }
                
                clusters[best_cluster].push(idx);
            }
            
            // 重新计算中心点
            let mut converged = true;
            for (c_idx, cluster) in clusters.iter().enumerate() {
                if cluster.is_empty() {
                    continue;
                }
                
                let mut new_center = vec![0.0f32; dim];
                for &node_idx in cluster {
                    for (d, val) in nodes[node_idx].1.vector.iter().enumerate() {
                        new_center[d] += val;
                    }
                }
                
                for d in 0..dim {
                    new_center[d] /= cluster.len() as f32;
                }
                
                // 检查是否收敛
                let shift = self.compute_distance(&centers[c_idx], &new_center);
                if shift > 0.01 {
                    converged = false;
                }
                
                centers[c_idx] = new_center;
            }
            
            println!("  K-Means iteration {}: {} non-empty clusters", iter + 1, 
                clusters.iter().filter(|c| !c.is_empty()).count());
            
            if converged {
                println!("  Converged after {} iterations", iter + 1);
                break;
            }
        }
        
        // 3. 为每个簇选择最接近中心的节点作为锚点
        let mut anchor_points = Vec::new();
        
        for center in centers.iter() {
            let mut min_dist = f32::MAX;
            let mut best_id = nodes[0].0;
            
            for (id, node) in nodes.iter() {
                let dist = self.compute_distance(&node.vector, center);
                if dist < min_dist {
                    min_dist = dist;
                    best_id = *id;
                }
            }
            
            anchor_points.push(best_id);
        }
        
        println!("[FreshDiskANN] Selected {} anchor points: {:?}", anchor_points.len(), anchor_points);
        Ok(anchor_points)
    }
    
    /// Phase 6: 选择 medoid（距离中心点）- 保留用于向后兼容
    #[allow(dead_code)]
    fn select_medoid(&self, nodes: &[(RowId, VectorNode)]) -> Result<RowId> {
        // 🔥 Phase 9: 使用 K-Means 选择第一个锚点作为 medoid
        let anchors = self.select_anchor_points(nodes, 1)?;
        Ok(anchors[0])
    }
    
    /// 计算两个向量的距离
    fn compute_distance(&self, v1: &[f32], v2: &[f32]) -> f32 {
        self.metric.distance(v1, v2)
    }
    
    /// 手动 Flush
    pub fn flush(&mut self) -> Result<()> {
        if !self.fresh_graph.is_empty() {
            self.flush_fresh_graph()?;
        }
        Ok(())
    }
    
    /// 获取统计信息
    pub fn stats(&self) -> FreshDiskANNStats {
        FreshDiskANNStats {
            fresh_count: self.fresh_graph.node_count(),
            fresh_memory: self.fresh_graph.memory_usage(),
            l1_sst_count: self.level1_ssts.len(),
            l1_total_nodes: self.level1_ssts.iter()
                .map(|sst| sst.metadata().node_count)
                .sum(),
            l2_nodes: self.merged_index.as_ref()
                .map(|sst| sst.metadata().node_count)
                .unwrap_or(0),
        }
    }
}

/// FreshDiskANN 统计信息
#[derive(Debug)]
pub struct FreshDiskANNStats {
    pub fresh_count: usize,
    pub fresh_memory: usize,
    pub l1_sst_count: usize,
    pub l1_total_nodes: u64,
    pub l2_nodes: u64,
}

// ==================== 🚀 Batch Index Builder Implementation ====================

use crate::index::builder::{IndexBuilder, BuildStats};
use crate::types::{Row, Value};

impl IndexBuilder for FreshDiskANNIndex {
    /// 批量构建向量索引（从MemTable flush时调用）
    fn build_from_memtable(&mut self, rows: &[(RowId, Row)]) -> Result<()> {
        use std::time::Instant;
        let start = Instant::now();
        
        // 🚀 Phase 1: 批量收集所有向量
        let mut vectors: Vec<(RowId, Vec<f32>)> = Vec::with_capacity(rows.len());
        
        for (row_id, row) in rows {
            // 遍历row中的所有列，找到Vector类型
            for value in row.iter() {
                if let Value::Vector(vec) = value {
                    vectors.push((*row_id, vec.to_vec()));
                    break; // 只取第一个向量列
                }
            }
        }
        
        if vectors.is_empty() {
            return Ok(());
        }
        
        println!("[FreshDiskANN] Batch building {} vectors", vectors.len());
        
        // 🔥 Phase 2: 根据数量选择策略
        if vectors.len() >= 1000 {
            // ✅ 大批量：使用标准Vamana批量构建（最优）
            println!("[FreshDiskANN] Using batch Vamana build (>= 1000 vectors)");
            self.batch_vamana_build(&vectors)?;
        } else {
            // ⚡ 小批量：增量插入到Fresh Graph
            println!("[FreshDiskANN] Using incremental insert (< 1000 vectors)");
            for (row_id, vec) in vectors {
                self.fresh_graph.insert(row_id, vec)?;
            }
            
            // 检查是否需要flush
            if self.fresh_graph.should_flush() {
                self.flush_fresh_graph()?;
            }
        }
        
        let duration = start.elapsed();
        println!("[FreshDiskANN] Batch build complete in {:?}", duration);
        
        Ok(())
    }
    
    /// 持久化索引到磁盘
    fn persist(&mut self) -> Result<()> {
        use std::time::Instant;
        let start = Instant::now();
        
        // Flush Fresh Graph到L1 SST（如果有数据）
        if !self.fresh_graph.is_empty() {
            self.flush_fresh_graph()?;
        }
        
        let duration = start.elapsed();
        println!("[FreshDiskANN] Persist complete in {:?}", duration);
        
        Ok(())
    }
    
    /// 获取索引名称
    fn name(&self) -> &str {
        "FreshDiskANN"
    }
    
    /// 获取构建统计信息
    fn stats(&self) -> BuildStats {
        let stats = self.stats();
        BuildStats {
            rows_processed: stats.fresh_count + stats.l1_total_nodes as usize,
            build_time_ms: 0, // 在实际实现中应该记录
            persist_time_ms: 0,
            index_size_bytes: stats.fresh_memory,
        }
    }
}

impl FreshDiskANNIndex {
    /// 🚀 批量Vamana构建（大批量优化）
    /// 
    /// 直接构建完整的Vamana图，比增量插入效率高10倍
    fn batch_vamana_build(&mut self, vectors: &[(RowId, Vec<f32>)]) -> Result<()> {
        use std::time::Instant;
        let start = Instant::now();
        
        // 1. 构建完整的Vamana图
        let mut graph_data: HashMap<RowId, VectorNode> = HashMap::new();
        
        // 1.1 初始化所有节点
        for (row_id, vec) in vectors {
            graph_data.insert(*row_id, VectorNode::new(vec.clone()));
        }
        
        // 1.2 选择medoid（中心点）
        let medoid = self.select_medoid_from_batch(vectors)?;
        println!("[FreshDiskANN] Selected medoid: {}", medoid);
        
        // 1.3 使用贪婪搜索构建邻居连接
        let r = self.config.fresh_config.max_degree;
        let _alpha = 1.2; // Vamana的alpha参数
        
        for (row_id, query_vec) in vectors {
            if *row_id == medoid {
                continue; // medoid特殊处理
            }
            
            // 搜索最近邻
            let mut candidates: Vec<(RowId, f32)> = Vec::new();
            
            for (other_id, other_vec) in vectors {
                if other_id != row_id {
                    let dist = self.metric.distance(query_vec, other_vec);
                    candidates.push((*other_id, dist));
                }
            }
            
            // 排序并取top-r
            candidates.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
            candidates.truncate(r);
            
            // 添加邻居
            if let Some(node) = graph_data.get_mut(row_id) {
                node.neighbors = candidates.into_iter().map(|(id, _)| id).collect();
            }
        }
        
        // 2. 将构建好的图直接插入到Fresh Graph
        // 简化版：逐个插入而不是写SST（避免复杂的持久化逻辑）
        for (row_id, vec) in vectors {
            self.fresh_graph.insert(*row_id, vec.clone())?;
        }
        
        let duration = start.elapsed();
        println!("[FreshDiskANN] Batch Vamana build: {} vectors in {:?}", 
            vectors.len(), duration);
        
        Ok(())
    }
    
    /// 从批量向量中选择medoid
    fn select_medoid_from_batch(&self, vectors: &[(RowId, Vec<f32>)]) -> Result<RowId> {
        if vectors.is_empty() {
            return Err(crate::StorageError::InvalidData("Empty vector batch".into()));
        }
        
        // 简单策略：选择离中心最近的点
        let dim = vectors[0].1.len();
        let mut center = vec![0.0f32; dim];
        
        // 计算中心点
        for (_, vec) in vectors {
            for (i, &v) in vec.iter().enumerate() {
                center[i] += v;
            }
        }
        
        let count = vectors.len() as f32;
        for c in center.iter_mut() {
            *c /= count;
        }
        
        // 找到最近的点
        let mut min_dist = f32::MAX;
        let mut medoid = vectors[0].0;
        
        for (row_id, vec) in vectors {
            let dist = self.metric.distance(vec, &center);
            if dist < min_dist {
                min_dist = dist;
                medoid = *row_id;
            }
        }
        
        Ok(medoid)
    }
}