# Persistence
`Index2D` and `Index3D` serialize to a stable little-endian byte format and load
back either as owned indexes or as zero-copy views. The binary layout is
documented in [`FORMAT.md`](https://github.com/Filyus/packed_spatial_index/blob/main/FORMAT.md).
```rust
use packed_spatial_index::{Index2D, Index2DBuilder, Index2DView, Box2D};
let mut builder = Index2DBuilder::new(1);
builder.add(Box2D::new(0.0, 0.0, 1.0, 1.0));
let index = builder.finish()?;
let bytes = index.to_bytes();
let mut reusable = Vec::new();
index.to_bytes_into(&mut reusable); // reuse one buffer across saves
assert_eq!(reusable, bytes);
let owned = Index2D::from_bytes(&bytes)?; // owns its tree
let view = Index2DView::from_bytes(&bytes)?; // borrows the bytes, no alloc
assert_eq!(owned.search(Box2D::new(0.0, 0.0, 2.0, 2.0)), vec![0]);
assert_eq!(view.search(Box2D::new(0.0, 0.0, 2.0, 2.0)), vec![0]);
# Ok::<(), Box<dyn std::error::Error>>(())
```
3D persistence uses the same container format, with the dimension recorded in the
`TREE` descriptor and six `f64` coordinates per stored box. With the `simd`
feature, `SimdIndex2D` and
`SimdIndex3D` read and write the same canonical bytes as the scalar indexes:
loading a SIMD index scatters the canonical box records into SoA columns, while
`SimdIndex2DView` / `SimdIndex3DView` borrow the same bytes for zero-copy
SIMD-over-AoS queries.
The compact `f32` indexes persist to their own `f32` box layout (`coord_bytes =
4`), halving the box bytes. With `f32-storage` the scalar `Index2DF32` /
`Index3DF32` build, query, `serialize()` (boxes plus an optional payload and
metadata), and `from_bytes` without `simd`; the SIMD `SimdIndex*F32` frontends
add the vectorized queries. The stored f32 boxes are rounded outward, so range
and ray results are a conservative superset — use `search_exact` (refining
against your `f64` boxes) when you need exact hits.
## Large / on-disk indexes (mmap)
Loaded buffers are validated before they can be searched, and the `*View` types
borrow the bytes without allocating an owned tree. That makes a memory-mapped
file the simple way to query an index that is large or lives on disk: map the
`PSINDEX` file, hand the byte slice to a view, and the OS pages in only the tree
nodes a query actually touches. This works for files larger than RAM — the
kernel evicts unused pages — and needs no extra crate API.
```rust,ignore
// Cargo.toml: memmap2 = "0.9"
use std::fs::File;
use memmap2::Mmap;
use packed_spatial_index::{Index2DView, Box2D};
let file = File::open("city.psindex")?;
// SAFETY: the file must not be mutated while mapped.
let mmap = unsafe { Mmap::map(&file)? };
let view = Index2DView::from_bytes(&mmap)?; // borrows the mapping, no copy
let hits = view.search(Box2D::new(0.0, 0.0, 100.0, 100.0));
# Ok::<(), Box<dyn std::error::Error>>(())
```
The crate stays dependency-free here: it only consumes `&[u8]`, so you pick the
mmap crate (`memmap2`, etc.). Storing the bytes as a database BLOB works the same
way once the blob is in memory — load it and call `from_bytes`.
## Streaming (out-of-core / remote)
For sources that cannot be memory-mapped — remote object storage, a database
blob you do not want to download whole — the `stream` feature queries a
serialized index by reading only the byte ranges a traversal needs. It works
over the **same `PSINDEX` bytes**; nothing special is needed at write time.
`StreamIndex2D` / `StreamIndex3D` open over any `RangeReader` (a one-method
trait: `read_exact_at`). The crate ships `FileReader` (local file, positioned
reads) and `SliceReader` (in-memory / mmap); a remote source is your own impl.
At open the reader validates the superblock and chunk directory and prefetches
the upper tree levels; each query then streams only the lower levels, coalescing
adjacent node ranges into few reads. Queries are fallible (a read can fail) and
return item indices like the in-memory `search`. Child pointers are validated as
they are followed, so the reader is safe on untrusted data.
```rust,ignore
// Cargo.toml: packed_spatial_index = { version = "0.7", features = ["stream"] }
use packed_spatial_index::{Box2D, FileReader, StreamIndex2D};
let reader = FileReader::open("planet.psindex")?;
let index = StreamIndex2D::open(reader)?;
let hits = index.search(Box2D::new(0.0, 0.0, 100.0, 100.0))?;
# Ok::<(), Box<dyn std::error::Error>>(())
```
For a remote source, implement `RangeReader` over HTTP range requests. It is one
method — return the bytes for `[offset, offset + len)`:
```rust,ignore
use packed_spatial_index::RangeReader;
use std::io::{self, Read};
struct HttpRange {
url: String,
}
impl RangeReader for HttpRange {
fn read_exact_at(&self, offset: u64, buf: &mut [u8]) -> io::Result<()> {
let end = offset + buf.len() as u64 - 1;
// Any HTTP client works; the request is a single ranged GET.
let resp = ureq::get(&self.url)
.set("Range", &format!("bytes={offset}-{end}"))
.call()
.map_err(io::Error::other)?;
resp.into_reader().read_exact(buf)
}
// Optional: returning the object size (e.g. from a HEAD request) lets `open`
// cross-check the declared length. `None` skips that check.
fn len(&self) -> Option<u64> {
None
}
}
```
The server only needs to honor the HTTP `Range` header — S3, R2, GCS, and most
CDNs do. For async I/O (a browser `fetch`, or a Cloudflare Worker over R2) enable
the `async` feature and implement `AsyncRangeReader` the same way; `open_async`,
`search_async`, and the async region/payload methods mirror sync streaming and
issue a level's reads concurrently.
**What streams today:** 2D and 3D range search (`search` / `search_into` /
`visit`), optionally returning a stored blob per hit (`search_payloads`, when the
file was written with `to_bytes_with_payloads`), sync or async. Streaming
readers also support region queries (`search_region` / `visit_region` /
`search_payloads_region` and their async counterparts) such as 2D convex
polygons and 3D frustums. All of these use optional per-query cost limits
(`open_with_limits` + `StreamLimits` —
bound reads, bytes, and items so a broad query cannot run unbounded). For a
remote-tuned layout, `to_bytes_interleaved` stores each node's box and child
pointer together so the descent fetches them in one read per level instead of
two.
**Cost in practice.** A query streams only the byte ranges its traversal
touches. Cost scales with the result rather than the file size, and the read
count is deterministic (machine-independent). The upper tree levels (the
"directory") are read once at `open`. With `into_directory` / `from_directory`
you reuse that parsed directory across queries and supply a fresh reader each
time, so its reads are never repaid. That is the pattern for one reader per
request. With the internal levels cached a small window over a 1M-item (about 100
MB) file streams roughly 6 ranged reads. Caching the whole tree drops a point
query to 1 or 2 reads, which happens for small files or with a larger
`StreamLimits::directory_budget_bytes`. The cached directory holds only the
internal levels (about `num_items / node_size` nodes, roughly 2.7 MB for 1M
items), so its footprint shrinks per item as the file grows. A runnable
Cloudflare Worker and R2 example lives in
[`wasm-demo/worker`](../wasm-demo/worker). It serves a 100 MB index straight from
object storage at about 6 range reads per query and uses roughly 10 MB of the
Worker's 128 MB isolate.
The second knob is `StreamLimits::coalesce_gap_bytes`: records (tree nodes or
payload blobs) within this many bytes of each other are fetched in one read. The
default is small (a few KB). Raising it to ~128-256 KB over-reads the gaps to
collapse round-trips, which is a strong win on a remote source and waste on a
local one, so set it for the source you have. It is bounded by `max_read_bytes`,
so a broad query still aborts rather than over-reading without limit. On a 1M
file a wide window drops from tens of reads to a handful with both this and a
roomy directory budget.
`StreamLimits::prefix_coalesce_gap_bytes` is the same knob for the queries that
read only the first few bytes of each matching payload. It defaults to the
requested prefix length, which never skips more than one prefix worth of bytes
and therefore never merges once bodies are larger than twice the prefix — so
such a scan issues one read per match. That is right for a local file and very
wrong over object storage; raise it there. See
[internals](internals/payload-prefix-scans.md) for the measured trade and the
body sizes at which it flips.
**Compact `f32` streaming:** `StreamIndex2DF32` / `StreamIndex3DF32` stream a
compact `f32`-box file for half the box bytes over the wire, with the same
sync and async `search` / `search_payloads` / `search_region` /
`search_payloads_region` API. The stored boxes are
rounded outward, so results are a conservative superset (filter against your own
`f64` boxes for exact). Write the file with the scalar `Index3DF32` or the SIMD
`SimdIndex3DF32`; `.interleaved()` on its `serialize()` builder enables the
one-read-per-level layout, and a triangle payload makes it a compact streamable
mesh BVH — all without the `simd` feature.
**What does not stream:** nearest-neighbor and raycast queries are in-memory only.
Their best-first traversal jumps around the tree, so adjacent reads do not
coalesce and streaming would be a read per node — load those with `from_bytes` or
a memory map instead.
Compared with a memory map, streaming trades per-query I/O for never needing the
whole file local or mapped — which is what makes a planet-scale index servable
straight from object storage. Untrusted and remote bytes are handled safely; see
[SAFETY.md](../SAFETY.md).