idb/innodb/
rtree.rs

1//! R-tree (spatial index) page parsing.
2//!
3//! InnoDB uses R-tree indexes for spatial data types (GEOMETRY, POINT, etc.).
4//! R-tree pages share the same INDEX page header structure as B+Tree pages
5//! but store Minimum Bounding Rectangles (MBRs) as keys instead of row data.
6//!
7//! Each MBR is 32 bytes: four 8-byte IEEE 754 doubles representing
8//! `(min_x, min_y, max_x, max_y)` in BigEndian format.
9
10use byteorder::{BigEndian, ByteOrder};
11use serde::Serialize;
12
13use crate::innodb::index::IndexHeader;
14
15/// Size of a Minimum Bounding Rectangle in bytes (4 × f64).
16const MBR_SIZE: usize = 32;
17
18/// Parsed Minimum Bounding Rectangle from an R-tree record.
19///
20/// # Examples
21///
22/// ```
23/// use idb::innodb::rtree::MinimumBoundingRectangle;
24/// use byteorder::{BigEndian, ByteOrder};
25///
26/// let mut buf = vec![0u8; 32];
27/// BigEndian::write_f64(&mut buf[0..], 1.0);
28/// BigEndian::write_f64(&mut buf[8..], 2.0);
29/// BigEndian::write_f64(&mut buf[16..], 3.0);
30/// BigEndian::write_f64(&mut buf[24..], 4.0);
31///
32/// let mbr = MinimumBoundingRectangle::parse(&buf).unwrap();
33/// assert_eq!(mbr.min_x, 1.0);
34/// assert_eq!(mbr.min_y, 2.0);
35/// assert_eq!(mbr.max_x, 3.0);
36/// assert_eq!(mbr.max_y, 4.0);
37/// ```
38#[derive(Debug, Clone, Serialize)]
39pub struct MinimumBoundingRectangle {
40    pub min_x: f64,
41    pub min_y: f64,
42    pub max_x: f64,
43    pub max_y: f64,
44}
45
46impl MinimumBoundingRectangle {
47    /// Parse an MBR from a 32-byte buffer.
48    pub fn parse(data: &[u8]) -> Option<Self> {
49        if data.len() < MBR_SIZE {
50            return None;
51        }
52
53        Some(MinimumBoundingRectangle {
54            min_x: BigEndian::read_f64(&data[0..]),
55            min_y: BigEndian::read_f64(&data[8..]),
56            max_x: BigEndian::read_f64(&data[16..]),
57            max_y: BigEndian::read_f64(&data[24..]),
58        })
59    }
60
61    /// Returns the area of this bounding rectangle.
62    pub fn area(&self) -> f64 {
63        (self.max_x - self.min_x) * (self.max_y - self.min_y)
64    }
65
66    /// Returns the overall MBR that encloses all given MBRs.
67    pub fn enclosing(mbrs: &[MinimumBoundingRectangle]) -> Option<MinimumBoundingRectangle> {
68        if mbrs.is_empty() {
69            return None;
70        }
71        let mut min_x = f64::MAX;
72        let mut min_y = f64::MAX;
73        let mut max_x = f64::MIN;
74        let mut max_y = f64::MIN;
75        for m in mbrs {
76            if m.min_x < min_x {
77                min_x = m.min_x;
78            }
79            if m.min_y < min_y {
80                min_y = m.min_y;
81            }
82            if m.max_x > max_x {
83                max_x = m.max_x;
84            }
85            if m.max_y > max_y {
86                max_y = m.max_y;
87            }
88        }
89        Some(MinimumBoundingRectangle {
90            min_x,
91            min_y,
92            max_x,
93            max_y,
94        })
95    }
96}
97
98/// Parsed R-tree page information.
99///
100/// Reuses the standard INDEX page header for level and record count,
101/// then extracts MBRs from the record data area.
102#[derive(Debug, Clone, Serialize)]
103pub struct RtreePageInfo {
104    /// R-tree level (0 = leaf).
105    pub level: u16,
106    /// Number of user records on this page.
107    pub record_count: u16,
108    /// MBRs extracted from records on this page.
109    pub mbrs: Vec<MinimumBoundingRectangle>,
110    /// Enclosing MBR covering all records (if any).
111    #[serde(skip_serializing_if = "Option::is_none")]
112    pub enclosing_mbr: Option<MinimumBoundingRectangle>,
113}
114
115/// Parse an R-tree page and extract MBR data.
116///
117/// Uses the standard INDEX page header for level and record count. MBRs
118/// are extracted by scanning for 32-byte aligned record data after the
119/// page header area.
120///
121/// Returns `None` if the page is too small or the INDEX header can't be parsed.
122///
123/// # Examples
124///
125/// ```
126/// use idb::innodb::rtree::parse_rtree_page;
127/// use idb::innodb::constants::*;
128/// use byteorder::{BigEndian, ByteOrder};
129///
130/// let mut page = vec![0u8; 256];
131/// let base = FIL_PAGE_DATA;
132///
133/// // Set INDEX header fields
134/// BigEndian::write_u16(&mut page[base + PAGE_LEVEL..], 0); // leaf
135/// BigEndian::write_u16(&mut page[base + PAGE_N_RECS..], 1);
136///
137/// let info = parse_rtree_page(&page);
138/// assert!(info.is_some());
139/// let info = info.unwrap();
140/// assert_eq!(info.level, 0);
141/// assert_eq!(info.record_count, 1);
142/// ```
143pub fn parse_rtree_page(page_data: &[u8]) -> Option<RtreePageInfo> {
144    let idx_hdr = IndexHeader::parse(page_data)?;
145
146    // Records start after the INDEX header (36 bytes) + 2 FSEG headers (20 bytes)
147    // + infimum (13 bytes) + supremum (13 bytes) = 82 bytes from FIL_PAGE_DATA
148    // = offset 120 from page start
149    let record_area_start = 120;
150
151    let mut mbrs = Vec::new();
152    let n_recs = idx_hdr.n_recs as usize;
153
154    // Scan for MBRs in the record area
155    // Each R-tree record starts with a 5-byte compact record header,
156    // followed by the 32-byte MBR key, then a 4-byte child page pointer (non-leaf)
157    // or row data (leaf).
158    let mut offset = record_area_start;
159    let record_header_size = 5; // compact format record header
160
161    for _ in 0..n_recs {
162        let mbr_start = offset + record_header_size;
163        if mbr_start + MBR_SIZE > page_data.len() {
164            break;
165        }
166
167        if let Some(mbr) = MinimumBoundingRectangle::parse(&page_data[mbr_start..]) {
168            // Sanity check: skip obviously invalid MBRs (NaN or infinity)
169            if mbr.min_x.is_finite()
170                && mbr.min_y.is_finite()
171                && mbr.max_x.is_finite()
172                && mbr.max_y.is_finite()
173            {
174                mbrs.push(mbr);
175            }
176        }
177
178        // Move to next record: header + MBR + child pointer (4 bytes for non-leaf)
179        // For leaf: header + MBR + row data (variable)
180        // Use a conservative estimate of 5 + 32 + 4 = 41 bytes per record
181        offset += record_header_size + MBR_SIZE + 4;
182    }
183
184    let enclosing_mbr = MinimumBoundingRectangle::enclosing(&mbrs);
185
186    Some(RtreePageInfo {
187        level: idx_hdr.level,
188        record_count: idx_hdr.n_recs,
189        mbrs,
190        enclosing_mbr,
191    })
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197    use crate::innodb::constants::*;
198
199    #[test]
200    fn test_mbr_parse() {
201        let mut buf = vec![0u8; 32];
202        BigEndian::write_f64(&mut buf[0..], 1.0);
203        BigEndian::write_f64(&mut buf[8..], 2.0);
204        BigEndian::write_f64(&mut buf[16..], 3.0);
205        BigEndian::write_f64(&mut buf[24..], 4.0);
206
207        let mbr = MinimumBoundingRectangle::parse(&buf).unwrap();
208        assert_eq!(mbr.min_x, 1.0);
209        assert_eq!(mbr.min_y, 2.0);
210        assert_eq!(mbr.max_x, 3.0);
211        assert_eq!(mbr.max_y, 4.0);
212    }
213
214    #[test]
215    fn test_mbr_too_short() {
216        let buf = vec![0u8; 20];
217        assert!(MinimumBoundingRectangle::parse(&buf).is_none());
218    }
219
220    #[test]
221    fn test_mbr_area() {
222        let mbr = MinimumBoundingRectangle {
223            min_x: 0.0,
224            min_y: 0.0,
225            max_x: 10.0,
226            max_y: 5.0,
227        };
228        assert!((mbr.area() - 50.0).abs() < f64::EPSILON);
229    }
230
231    #[test]
232    fn test_mbr_enclosing() {
233        let mbrs = vec![
234            MinimumBoundingRectangle {
235                min_x: 1.0,
236                min_y: 2.0,
237                max_x: 5.0,
238                max_y: 6.0,
239            },
240            MinimumBoundingRectangle {
241                min_x: 3.0,
242                min_y: 1.0,
243                max_x: 10.0,
244                max_y: 8.0,
245            },
246        ];
247
248        let enc = MinimumBoundingRectangle::enclosing(&mbrs).unwrap();
249        assert_eq!(enc.min_x, 1.0);
250        assert_eq!(enc.min_y, 1.0);
251        assert_eq!(enc.max_x, 10.0);
252        assert_eq!(enc.max_y, 8.0);
253    }
254
255    #[test]
256    fn test_mbr_enclosing_empty() {
257        assert!(MinimumBoundingRectangle::enclosing(&[]).is_none());
258    }
259
260    #[test]
261    fn test_parse_rtree_page_basic() {
262        let mut page = vec![0u8; 256];
263        let base = FIL_PAGE_DATA;
264
265        // Set INDEX header: level=0, n_recs=1
266        BigEndian::write_u16(&mut page[base + PAGE_LEVEL..], 0);
267        BigEndian::write_u16(&mut page[base + PAGE_N_RECS..], 1);
268
269        // Write an MBR at record area (offset 120 + 5 byte record header)
270        let mbr_offset = 125;
271        BigEndian::write_f64(&mut page[mbr_offset..], 10.0);
272        BigEndian::write_f64(&mut page[mbr_offset + 8..], 20.0);
273        BigEndian::write_f64(&mut page[mbr_offset + 16..], 30.0);
274        BigEndian::write_f64(&mut page[mbr_offset + 24..], 40.0);
275
276        let info = parse_rtree_page(&page).unwrap();
277        assert_eq!(info.level, 0);
278        assert_eq!(info.record_count, 1);
279        assert_eq!(info.mbrs.len(), 1);
280        assert_eq!(info.mbrs[0].min_x, 10.0);
281        assert_eq!(info.mbrs[0].max_y, 40.0);
282        assert!(info.enclosing_mbr.is_some());
283    }
284
285    #[test]
286    fn test_parse_rtree_page_too_short() {
287        let page = vec![0u8; 30];
288        assert!(parse_rtree_page(&page).is_none());
289    }
290}
idb/innodb/rtree.rs

idb/innodb/
rtree.rs
