| 267 | } |
| 268 | |
| 269 | pub fn batch_insert(&mut self, entries: Vec<(K, V)>) -> Result<(), io::Error> { |
| 270 | if entries.is_empty() { |
| 271 | println!("No entries to insert"); |
| 272 | return Ok(()); |
| 273 | } |
| 274 | |
| 275 | let mut entries = entries; |
| 276 | entries.sort_by(|a, b| a.0.cmp(&b.0)); |
| 277 | |
| 278 | let entrypoint = self.find_entrypoint(entries[0].0.clone())?; |
| 279 | |
| 280 | let mut current_offset = entrypoint; |
| 281 | let mut node = self.storage_manager.load_node(current_offset)?; |
| 282 | |
| 283 | for (key, value) in entries.iter() { |
| 284 | while node.node_type == NodeType::Internal { |
| 285 | // We should only be operating on leaf nodes in this loop |
| 286 | let idx = node.keys.binary_search(key).unwrap_or_else(|x| x); |
| 287 | current_offset = node.children[idx]; |
| 288 | node = self.storage_manager.load_node(current_offset)?; |
| 289 | } |
| 290 | |
| 291 | if node.is_full() { |
| 292 | let (median, mut sibling) = node.split(self.b)?; |
| 293 | let sibling_offset = self.storage_manager.store_node(&mut sibling)?; |
| 294 | self.storage_manager.store_node(&mut node)?; // Store changes to the original node after splitting |
| 295 | |
| 296 | if node.is_root { |
| 297 | // println!("Creating new root"); |
| 298 | // Create a new root if the current node is the root |
| 299 | let mut new_root = Node::new_internal(0); |
| 300 | new_root.is_root = true; |
| 301 | new_root.keys.push(median.clone()); |
| 302 | new_root.children.push(current_offset); // old root offset |
| 303 | new_root.children.push(sibling_offset); // new sibling offset |
| 304 | new_root.parent_offset = None; |
| 305 | let new_root_offset = self.storage_manager.store_node(&mut new_root)?; |
| 306 | self.storage_manager.set_root_offset(new_root_offset); |
| 307 | node.is_root = false; |
| 308 | node.parent_offset = Some(new_root_offset); |
| 309 | sibling.parent_offset = Some(new_root_offset); |
| 310 | // println!("New root offset: {}", new_root_offset); |
| 311 | self.storage_manager.store_node(&mut node)?; |
| 312 | self.storage_manager.store_node(&mut sibling)?; |
| 313 | } else { |
| 314 | // Update the parent node with the new median |
| 315 | let parent_offset = node.parent_offset.unwrap(); |
| 316 | // println!("Parent offset: {}", parent_offset); |
| 317 | let mut parent = self.storage_manager.load_node(parent_offset)?; |
| 318 | let idx = parent |
| 319 | .keys |
| 320 | .binary_search(&median.clone()) |
| 321 | .unwrap_or_else(|x| x); |
| 322 | parent.keys.insert(idx, median.clone()); |
| 323 | parent.children.insert(idx + 1, sibling_offset); |
| 324 | self.storage_manager.store_node(&mut parent)?; |
| 325 | } |
| 326 | |