Method build

nodedb-array/src/segment/mbr_index/build.rs:33–79

Bulk-load from segment tile entries (assumed Hilbert-ordered by the writer). Time complexity O(n) — one pass per level.

(entries: &[TileEntry])

    /// Bulk-load from segment tile entries (assumed Hilbert-ordered by
    /// the writer). Time complexity O(n) — one pass per level.
    pub fn build(entries: &[TileEntry]) -> Self {
        let mut nodes: Vec<RNode> = Vec::new();
        if entries.is_empty() {
            return Self { nodes, root: None };
        }
        // Leaves — chunk consecutive tiles, recording each tile's
        // absolute index and individual bbox so per-tile filtering can
        // happen at leaf descent time.
        let mut current_level: Vec<usize> = Vec::new();
        let mut cursor = 0usize;
        for chunk in entries.chunks(FANOUT) {
            let bbox = chunk_bbox(chunk);
            let tiles: Vec<(usize, BBox)> = chunk
                .iter()
                .enumerate()
                .map(|(i, e)| (cursor + i, BBox::from_mbr(&e.mbr)))
                .collect();
            cursor += chunk.len();
            nodes.push(RNode {
                bbox,
                kind: RNodeKind::Leaf { tiles },
            });
            current_level.push(nodes.len() - 1);
        }
        // Internal levels
        while current_level.len() > 1 {
            let mut next_level: Vec<usize> = Vec::new();
            for chunk in current_level.chunks(FANOUT) {
                let mut bbox = BBox {
                    min: vec![],
                    max: vec![],
                };
                for &child in chunk {
                    bbox.extend(&nodes[child].bbox);
                }
                let children = chunk.to_vec();
                nodes.push(RNode {
                    bbox,
                    kind: RNodeKind::Internal { children },
                });
                next_level.push(nodes.len() - 1);
            }
            current_level = next_level;
        }
        let root = current_level.first().copied();
        Self { nodes, root }
    }

    pub fn node_count(&self) -> usize {
        self.nodes.len()