A method of storing data in a database, said database containing data stored in a tree structure, said tree structure including a plurality of nodes, a node having associated data comprising: two node pointers, said node pointers comprising data identifying nodes which may be traversed when searching said tree structure; a node key, and a search key part identifier identifying a search key part to be used to determine a node pointer to be used when traversing the node, wherein a particular node's search key part identifier relates to a search key bit to be used to determine a node pointer of the two node pointers to be used when traversing the particular node, wherein said method comprises inserting a new node into said tree structure, said new node having an associated node key, said inserting comprising: searching said database by traversing nodes of said tree structure using an insertion search key, said insertion search key comprising said new node key, said searching using said insertion search key to identify (606; 608; 612) a node in said tree structure whose node key is prefixed by said insertion search key; inserting (616; 618; 620) said new node into said tree structure above said identified node in said tree structure; and allocating to said new node: two node pointers comprising a pointer from said new node to a node above said new node in said tree structure whose node key prefixes the node key of said new node; a node key equal to said insertion search key (708; 808; 908); and a search key part identifier equal to the search key part identifier of the node above said new node in said tree structure (710; 810; 910). two node pointers, said node pointers comprising data identifying nodes which may be traversed when searching said tree structure; a node key, and a search key part identifier identifying a search key part to be used to determine a node pointer to be used when traversing the node, wherein a particular node's search key part identifier relates to a search key bit to be used to determine a node pointer of the two node pointers to be used when traversing the particular node, wherein said method comprises inserting a new node into said tree structure, said new node having an associated node key, said inserting comprising: searching said database by traversing nodes of said tree structure using an insertion search key, said insertion search key comprising said new node key, said searching using said insertion search key to identify (606; 608; 612) a node in said tree structure whose node key is prefixed by said insertion search key; inserting (616; 618; 620) said new node into said tree structure above said identified node in said tree structure; and allocating to said new node: two node pointers comprising a pointer from said new node to a node above said new node in said tree structure whose node key prefixes the node key of said new node; a node key equal to said insertion search key (708; 808; 908); and a search key part identifier equal to the search key part identifier of the node above said new node in said tree structure (710; 810; 910). searching said database by traversing nodes of said tree structure using an insertion search key, said insertion search key comprising said new node key, said searching using said insertion search key to identify (606; 608; 612) a node in said tree structure whose node key is prefixed by said insertion search key; inserting (616; 618; 620) said new node into said tree structure above said identified node in said tree structure; and allocating to said new node: two node pointers comprising a pointer from said new node to a node above said new node in said tree structure whose node key prefixes the node key of said new node; a node key equal to said insertion search key (708; 808; 908); and a search key part identifier equal to the search key part identifier of the node above said new node in said tree structure (710; 810; 910). two node pointers comprising a pointer from said new node to a node above said new node in said tree structure whose node key prefixes the node key of said new node; a node key equal to said insertion search key (708; 808; 908); and a search key part identifier equal to the search key part identifier of the node above said new node in said tree structure (710; 810; 910).