Geospatiale Indizierung für die Verteidigung: H3, S2, R-Tree und die Millionen-Track-Abfrage

Das Millionen-Track-Abfrageproblem

Eine häufige Operator-Abfrage in einer Verteidigungs-Fusionsplattform lautet: „Zeige mir alles innerhalb von 5 km um diesen Punkt in den letzten 60 Sekunden." Es klingt trivial. Auf einer Tabelle mit hundert Millionen Track-Updates, geschrieben von AIS-Empfängern, ADS-B-Feeds, Radar-Tracks, ESM und Drohnen-Telemetrie, kollabiert eine naive Implementierung innerhalb von drei Wochen Produktionsverkehr.

Die naive Abfrage ist ein sequentieller Scan. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. Auf einer Hundert-Millionen-Zeilen-Tabelle ohne räumlichen Index sind das 12 bis 40 Sekunden je nach Festplatte. Mit tausend Operatoren, die alle 2 Sekunden aktualisieren, brennt die Datenbank. Die Lösung ist nicht schnellere Hardware. Die Lösung ist ein räumlicher Index — und die Indexwahl diktiert alles Nachgelagerte: Ingest-Durchsatz, Abfrage-Latenz, Speicher-Footprint und die Kosten verteilten Shardings.

Dieser Artikel geht die vier Indexfamilien durch, die für die Verteidigung relevant sind: H3, S2, die R-Tree-Linie und das PostGIS GiST/SP-GiST/BRIN-Trio. Dann werden die hybriden Zeitreihen-Muster, die Dual-Layer-Culling-Architektur für das gemeinsame Lagebild und die Migrationsgeschichte behandelt.

H3 (Uber Hexagonal)

H3 ist ein hierarchisches hexagonales Gittersystem. Der Planet wird in 122 Basis-Zellen aufgeteilt (10 Pentagone, 112 Hexagone), und jede Basis-Zelle unterteilt sich rekursiv in sieben Kinder, bis zu Auflösung 15. Eine Zelle bei Auflösung 9 ist etwa 0,1 km² — die Größe eines Stadtblocks. Eine Zelle bei Auflösung 6 ist etwa 36 km² — eine nützliche operative Einsatzblase.

Hexagone schlagen Quadrate für Proximity-Abfragen, weil jeder hexagonale Nachbar denselben Zentroid-Abstand hat. Bei einem Quadratgitter sind diagonale Nachbarn 1,41× weiter entfernt als Kantennachbarn — jede Distanzberechnung muss das speziell behandeln. Bei Hexagonen liefert ein k-ring mit Radius 3 genau 37 Zellen, alle in vorhersagbarem Abstand. Eine 5-km-Radius-Suche wird zu: Abfragepunkt in eine H3-Zelle konvertieren, auf einen k-Ring erweitern, der 5 km abdeckt, alle mit diesen Zell-IDs getaggten Tracks abrufen und dann mit exaktem ST_Distance verfeinern.

Verteidigungs-freundliche Eigenschaften: H3-Zell-IDs sind 64-Bit-Integer, trivial in jedem KV-Store zu indizieren. Die Zellmitgliedschaft ist hashbar, sodass ein Track mit einer H3-Spalte nach Zell-Präfix ohne maßgeschneiderte Logik gesharded werden kann. Zell-Aggregate auf Zellenebene („Wie viele Tracks pro H3-7-Zelle in der letzten Stunde") kollabieren direkt auf ein GROUP BY h3_index. Wir haben H3-indizierte Track-Tabellen gesehen, die 5-km-Proximity-Abfragen in 8–14 ms auf Tabellen mit 200 Millionen Zeilen beantworten.

Google S2

S2 partitioniert die Sphäre über eine Quadtree-Projektion auf die Oberfläche eines eingeschriebenen Würfels. Jede Fläche wird rekursiv in vier Kinder unterteilt, bis zu Level 30, wo Zellen etwa 1 cm² groß sind. Die S2CellId ist ein 64-Bit-Integer, der Zellfläche, Position entlang einer Hilbert-Kurve und Level kodiert. Die Hilbert-Kodierung ist der Trick: Zellen, die auf der Sphäre nahe beieinander liegen, haben nahe IDs, sodass sich ein BETWEEN-Range auf der Integer-Spalte wie eine räumliche Range-Abfrage verhält.

Dieser Integer-Arithmetik-Vorteil ist, wo S2 gewinnt. Wenn der Arbeitsstore ein gesharded RDBMS, ein flacher KV (DynamoDB, Cassandra) oder eine Suchmaschine ist (Elasticsearchs geo_shape verwendet BKD-Bäume, aber Range-Abfragen auf S2CellIds sind gleich schnell), hält S2 die Proximity-Logik innerhalb günstiger Integer-Vergleiche. Keine GIS-Erweiterung erforderlich.

H3 versus S2 in der Praxis: H3 ist freundlicher für gleichmäßiges-Distanz-Reasoning, Aggregationen und menschenlesbare Zellen. S2 ist freundlicher, wenn die Speicherschicht keine Geometrie-Unterstützung hat und Sie mit Milliarden von Punkten über globale Abdeckung arbeiten, wo Pentagon-Verzerrung in H3 (10 Zellen pro Planet haben nur 5 Nachbarn statt 6) Probleme erzeugt. NATO-Maritime-Überwachungsteams, die globale AIS-Daten indizieren, sind genau aus diesem Grund auf S2 umgezogen. Regionale Luftbilder mit kontinentaler Reichweite bleiben meist auf H3.

R-Tree und Varianten

Der R-Tree, eingeführt von Guttman 1984, indiziert Geometrien nach Bounding-Boxen. Jeder Baumknoten speichert das minimale Bounding-Rectangle (MBR) seiner Kinder. Eine Proximity-Abfrage durchläuft den Baum und beschneidet Teilbäume, deren MBR die Abfrage-Hülle nicht schneidet. Der Worst Case ist schlecht — Überlappung zwischen MBRs degradiert zu linearem Scan — aber der durchschnittliche Fall auf realen Daten ist exzellent.

R*-Tree (1990) reduziert MBR-Überlappung mit klügeren Knoten-Splits und Reinsertion beim Overflow. Es ist die Variante, die die meisten Produktionssysteme heute implementieren, einschließlich des In-Memory-R-Tree innerhalb von libspatialindex, das von GeoPandas und der Spatial-Extension von DuckDB verwendet wird.

Die Bulk-Load-Geschichte zählt. Eine Million Geometrien einzeln in einen R-Tree zu laden ist langsam und erzeugt einen schlecht balancierten Baum. Der Sort-Tile-Recursive (STR)-Bulk-Load baut den gesamten Baum in einem einzigen Durchlauf, nachdem Geometrien entlang einer raumfüllenden Kurve sortiert wurden, und liefert ein nahezu optimales MBR-Layout. Verwenden Sie immer Bulk-Load, wenn Sie einen neuen Index auf einem zurückgefüllten Datensatz erstellen.

Wann der In-Memory-R-Tree noch gewinnt: Client-seitige Geometrie-Indizes innerhalb einer einzelnen Operator-Workstation (Qt-basierte Common-Operational-Picture-Clients, browserseitige Leaflet-/Mapbox-Supercluster-Layer) und zustandslose Geofence-Dienste, bei denen das Geofence-Set in den RAM passt. Ein 100k-Geofence-R-Tree in libspatialindex bedient Point-in-Polygon-Lookups in 30–60 µs. PostGIS für die gleiche Arbeitslast, mit Netzwerk-Round-Trip, ist näher an 1–2 ms.

PostGIS-Indizierung — GiST vs. SP-GiST vs. BRIN

PostGIS ist das Standard-Geospatial-Rückgrat für die meisten Verteidigungs-Fusion-Stacks, die Corvus berührt hat, und die Indexwahl darin ist nicht trivial. Siehe unseren tieferen PostGIS-für-Verteidigung-Leitfaden für das volle Setup; dieser Abschnitt ist die Indexauswahl-Zusammenfassung.

GiST ist der Generalized-Search-Tree, den PostGIS verwendet, um ein R-Tree-Äquivalent über Geometrien zu implementieren. Es ist der Standard. Passt gut, wenn Geometrien in der Größe heterogen sind (Punkte, Linien, Polygone mischen) und wenn die Arbeitslast Lesen und Schreiben mischt. Build-Zeit auf 100M-Punkt-Zeilen beträgt etwa 15–25 Minuten auf einer schnellen SSD mit auf 2 GB getuntem maintenance_work_mem.

SP-GiST (raum-partitionierter GiST) implementiert Quadtrees und k-d-Trees. Schneller bei reinen Punkt-Arbeitslasten, wo Daten gleichmäßig verteilt sind. Wir haben SP-GiST 1,4–1,8× schneller als GiST für reine Punkt-Proximity-Abfragen auf einer 50M-Zeilen-Track-Tabelle gemessen, mit 25 % kleinerem Index-Footprint.

BRIN (Block Range Index) ist die günstige Option, wenn Daten bereits physisch nach Standort geclustert sind — zum Beispiel, wenn Track-Inserts nach Region partitioniert und physisch in geografischer Reihenfolge angehängt werden. BRIN-Indizes sind winzig (Kilobyte für Tabellen, die Gigabyte GiST benötigen) und als sekundärer Filter nützlich, nicht als primärer räumlicher Index. Sie glänzen auf kalten Archiv-Partitionen.

Das räumlich-zeitlich kombinierte Indexmuster: Für „innerhalb von 5 km in den letzten 60 Sekunden"-Arbeitslasten versuchen Sie nicht, einen einzigen Multi-Spalten-Index zu bauen. Bauen Sie stattdessen einen GiST auf geom und einen B-Tree auf ts und partitionieren Sie die Tabelle dann nach Zeit. Der Abfrageplaner kombiniert beide, und Partition-Pruning eliminiert 99 % der Daten, bevor irgendeine räumliche Arbeit geschieht. Echte Abfragepläne auf Millionen-Zeilen-Partitionen antworten in 4–12 ms. Dieselbe Abfrage ohne Partition-Pruning, auf derselben indizierten Tabelle, ist 200–400 ms.

Zeitreihen + geospatialer Hybrid

Verteidigungs-Tracks sind im Kern Zeitreihen. Jedes Track-Update ist ein Append. Lesevorgänge sind überwiegend „letzte Position pro Emitter" und „Spur der letzten N Minuten". Der Hybrid-Stack zählt.

TimescaleDB-Hypertables mit PostGIS. Eine Hypertable partitioniert automatisch nach Zeitchunks (1-Stunden- oder 6-Stunden-Chunks für Feeds mit hohem Volumen). PostGIS-GiST-Indizes werden pro Chunk gebaut. Kompression auf Chunks älter als 24 Stunden liefert 8–14× Speicherreduktion. Kontinuierliche Aggregate berechnen Pro-H3-Zelle stündliche Zusammenfassungen vor. Dies ist der empfohlene Start-Stack für die meisten Verteidigungs-Fusion-Deployments.

kdb+/q für die höchsten Durchsatzfälle. Wenn die Plattform mehrere hunderttausend Track-Updates pro Sekunde absorbieren muss — große Radarnetze fusioniert mit Multi-Source-ESM — bleibt kdb+ Columnar-Storage mit q-sql Best-of-Breed. q-sql ist asketisch, die Lizenzierung ist teuer, aber der Durchsatz ist real. Die geospatiale Geschichte ist handgerollt (H3- oder S2-Zell-IDs als reguläre Long-Spalten) statt einer nativen GIS-Erweiterung.

ClickHouse mit Geohash-Spalten. ClickHouse handhabt die analytische Replay-Schicht gut — die letzten sieben Tage Tracks gegen einen neuen Korrelationsalgorithmus replayen. Geohash-Spalten (variable-Länge Base32-Strings, Präfix-Gleichheit = Bounding-Box-Containment) sind der pragmatische Index. ClickHouse 24.x fügte native geoDistance- und S2-Funktionen hinzu; auf einer 5-Milliarden-Zeilen-historischen-Track-Tabelle löst sich ein 10-km-Proximity-Scan in 1–3 Sekunden. Nicht interaktiv, aber akzeptabel für Analyst-Arbeitslasten.

Indizes für das Lagebild

Das gemeinsame Lagebild (COP) ist der kanonische Konsument von geospatialen Indizes. Hunderte bis Tausende von Operator-Sitzungen, jede rendert Tracks innerhalb eines Viewports und aktualisiert 1–4 Mal pro Sekunde. Ohne eine Dual-Layer-Culling-Architektur stirbt das Backend zuerst.

Serverseitiges Culling. Der Server wendet die Viewport-Bounding-Box als räumliche Indexabfrage an, dann den Zeitfenster-Filter, dann Entitätstyp- und Freigabe-Filter. Das Ergebnis ist eine begrenzte Nutzlast — typischerweise auf 5.000 Tracks pro Antwort gedeckelt, um die Drahtgröße vorhersagbar zu halten. Auf einer ordnungsgemäß indizierten PostGIS-Hypertable sind das 6–20 ms pro Sitzung.

Clientseitiges Culling. Der Client erhält eine etwas größere Hülle als den sichtbaren Viewport (damit Schwenken nicht sofort einen Refetch auslöst), pflegt einen In-Memory-R-Tree von Tracks und rendert nur, was innerhalb der sichtbaren Leinwand liegt. Der R-Tree behandelt Schwenken, Zoomen und Hover-Hit-Testing lokal bei 60 FPS ohne Server-Round-Trips.

Die Dual-Layer ist, was auf Tausende gleichzeitiger Sitzungen skaliert. Serverseitiges Culling deckelt Backend-Kosten. Clientseitiges Culling deckelt Frontend-Kosten. Eine Schicht alleine bricht. Dieses Muster ist essentiell, ob das COP ein Thick-Client (Qt, .NET) oder eine Browser-Karte (Mapbox GL, MapLibre, deck.gl) ist — siehe die breitere Pipeline-Referenz in Teil 1 unserer Verteidigungs-Fusion-Pipeline-Serie.

Migrationsrealitäten

Die Migration von „alles in einer einzigen Tabelle ohne räumlichen Index" zu einem ordnungsgemäß indizierten, partitionierten, hypertable-gestützten Store ist, wo die meisten Verteidigungs-Datenprogramme stolpern. Drei Regeln aus der Lieferungserfahrung:

Dual-Write vor Cutover. Der neue indizierte Store läuft parallel zur Legacy-Tabelle für mindestens zwei operative Zyklen (typischerweise zwei Wochen). Schreibvorgänge gehen an beide. Lesevorgänge verlagern sich allmählich. Rollback ist ein Config-Flag, keine Datenbankmigration.

Schema-Evolutions-Disziplin. Das Hinzufügen einer Spalte zu einer 500-GB-Hypertable mit voller GiST-Indizierung ist kein 5-Sekunden-ALTER TABLE. Planen Sie Spaltenerweiterungen als bewusste Releases. Verwenden Sie JSONB-Payloads für Felder unter Experimentation; promovieren Sie stabile Felder zu typisierten Spalten, sobald sich das Schema gesetzt hat.

Backfill in zeitgeordneten Chunks. Das Wiederherstellen historischer Track-Daten in die neue Hypertable in umgekehrt chronologischer Reihenfolge (neueste zuerst) bedeutet, dass das operativ relevante Fenster zuerst abfragbar ist, während ältere Chunks im Hintergrund ingestiert werden. Warten Sie nicht auf den vollständigen Backfill, bevor Sie Lesevorgänge umstellen.