1	sub B_search {
     2	  my $self = shift;
     3	  my %args = @_;
     4	  my $cur_node = $self->root;
     5	  my $k = $args{Key};
     6	  my $d = $args{Data};
     7	  my @path;
     8	
     9	  if ($cur_node->is_empty) {	# Special case for empty root
    10	    if ($args{Insert}) {
    11	      $cur_node->insert_kdp($k => $d);
    12	      return $d;
    13	    } else {
    14	      return undef;
    15	    }
    16	  }
    17	
    18	  # Descend tree to leaf
    19	  for (;;) {
    20	
    21	    # Didn't hit bottom yet.
    22	
    23	    my($there, $where) = $cur_node->locate_key($k);
    24	    if ($there) {		# Found it!
    25	      if ($args{Replace}) {
    26		$cur_node->kdp($where, $k => $d);
    27	      } 
    28	      return $cur_node->data($where);
    29	    }
    30	    
    31	    # Not here---must be in a subtree.
    32	    
    33	    if ($cur_node->is_leaf) {	# But there are no subtrees
    34	      return undef unless $args{Insert}; # Search failed
    35	      # Stuff it in
    36	      $cur_node->insert_kdp($k => $d);
    37	      if ($self->node_overfull($cur_node)) { # Oops--there was no room.
    38		$self->split_and_promote($cur_node, @path);
    39	      } 
    40	      return $d;
    41	    }
    42	
    43	    # There are subtrees, and the key is in one of them.
    44	
    45	    push @path, [$cur_node, $where];	# Record path from root.
    46	
    47	    # Move down to search the subtree
    48	    $cur_node = $cur_node->subnode($where);
    49	
    50	    # and start over.
    51	  }				# for (;;) ...
    52	
    53	  croak ("How did I get here?");
    54	}