Modified Skip List Database Structure and Method for Access

1. Field Of The Invention

The invention relates to systems and methods for in-memory database access, and more particularly to systems and methods for insertion, deletion and access in a database organized as a skip list using compressed search keys.

2. Background Information

Telecommunications networks use databases to store very large amounts of information. One such application is the translation of 800 telephone numbers to geographic termination numbers. Another application is validation of credit card calls. In both applications, there are millions of records which must be searched. The search must be performed while a customer is waiting for a call to be completed, so it must be completed within a few seconds. Large numbers of search requests may arrive simultaneously, but again, each search cannot take more than a few seconds. Current art disk-based database systems do not have the throughput to meet these requirements. Therefore, current art systems are generally memory based.

Since a database may contain millions of records, a memory-based database system must contain a large amount of memory. Systems having one gigabyte of main memory are not unusual. Nevertheless, increased calling, internationalization of credit cards and increasing users of 800 numbers have increased the size of such databases to the point that even one gigabyte may not be sufficient. Systems with more memory are possible, but their cost is very high.

A better solution to the problem is to compress the database. Compression of the data fields is well known in the art, but additional memory usage improvement can be had by compressing the key values as well. One way to compress key values is to store the nodes in sorted order by key value with the search key for each node based on the difference between the key value for that node and the key value for the previous node. The problem is to create an in memory data structure that allows both key compression and quick indexed retrieval.

3. Other Publications

W. Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM, 33(6)668-676(1990).

W. Pugh, A Skip List Cookbook, University of Maryland (1990).

An object of the invention is an in memory data structure with compressed search keys which allows quick indexed retrieval.

Another object is a system and method for insertion, deletion and access to data stored in a skip list having compressed keys

These and other objects and advantages are accomplished by a modified skip list data structure. A skip list data structure in accordance with the present invention is a linked list in which some of the nodes have more than one pointer. The number of pointers contained in a node is determined when the node is created and is usually not changed. Every node has at least one pointer which may point to another node. Other nodes have additional pointers which point to nodes further down the list. When the list is searched by following the pointers, the additional pointers allow the search to skip over many of the nodes. This improves searching performance.

Each node contains an element and at least one pointer. The element contains a search key which is a compressed representation of a key value which is used to identify the desired node for a search. The element may also contain data. The presence of compressed search keys allows the present invention to use significantly less memory than the current art to store a given amount of data. The search key for a particular node is generated based on the difference between the key value of that node and the key value of the node which points to that node. The prior art skip list structure allowed a node to be pointed to by multiple other nodes, and did not have compressed search keys. The search key compression method of the present invention could not be used with prior art skip lists because a node could be pointed to by multiple other nodes. Because of the search key compression of the present invention, the present invention skip list structure has been modified to ensure that each node is pointed to by only one other node.

A search of the data structure is begun using the highest level pointers, that is the pointers which skip over the most nodes. Since the list is in sorted order, it is simple to detect when the search has gone too far. In this case, the search goes back to the previous node and drops down to a lower level pointer in order to search some of the nodes which were previously skipped over. The search continues in this way until the desired node is found or until the node cannot be found and the search is at the lowest level.

FIG. 1 is a block diagram of a database system in accordance with the invention.

FIG. 2a is a block diagram of an embodiment of a modified SKL database structure 200 in the database system of FIG. 1.

FIG. 2b is a block diagram of an embodiment of a node of a modified SKL database structure in the database system of FIG. 1.

FIG. 3 is a flow diagram of read routine 120 for use with the database structure of FIG. 2.

FIG. 4 is a flow diagram of replace routine 122 for use with the database structure of FIG. 2. FIG. 5a is a flow diagram of add routine 124 for use with the database structure of FIG. 2. FIG. 5b is a flow diagram of a subprocess of step 504 of FIG. 5a.

FIG. 6 is a flow diagram of delete routine 126 for use with the database structure of FIG. 2.

FIG. 1 is a block diagram of a database system 100 with a skip list (SKL) database. The system includes CPU 102, I/O adapter 104, operator interface 106, disk 108 and memory 110 which are all connected by bus 112. I/O adapter 104 is connected to communications network 118. Memory 110 includes SKL partition 116 which contains SKL database structure 200 and read routine 120, replace routine 122, insert routine 124 and delete routine 126 for use with SKL database structure 200. Memory 110 also includes operating system 130.

FIG. 2a is a block diagram of an embodiment of a modified SKL database structure 200 in the database system of FIG. 1. Root node 201 is shown as including seven pointers: level 0 pointer 202 which points to node 210, level 1 pointer 203 which points to node 220, level 2 pointer 204 which points to node 240, level 3 pointer 205 which is 0, level 4 pointer 206 which is 20, level 5 pointer 207 which is 0 and level 6 pointer 208 which is 0. A pointer of 0 indicates that the pointer does not point to another node. Nine nodes 210, 220, 230, 240, 250, 260, 270, 280 and 290 are shown. Each node contains an element 219, 229, 239, 249, 259, 269, 279, 289 and 299 respectively. Each element contains a search key 211, 221, 231, 241, 251, 261, 271, 281 and 291 respectively which represent key values AAA, AAB, AAD, AAE, ABA, ABB, ABC, ACA and ACB respectively. Each element also contains an optional data field 213, 224, 233, 245, 254, 263, 275, 283 and 293 respectively. Each key value is compressed to form the search key based on the key value of the previous node in the list. The key values are shown to aid in understanding the figure, but are not part of the data structure.

The search key of a particular node includes the number of initial characters of the key value for that node which are the same as in the key value for the previous node, plus the remaining characters which are different. For example, Node 240 is subsequent to root node 201, so node 240 has search key 241 which is AAE, the same as the key value. Mode 240 is previous to node 270, which has search key 271 equal to 1BC. The initial character of both key values is A, so search key 271 begins with 1. The remaining characters of the key value for node 270 are BC, so search key 271 contains 1 plus BC. The search key of the first node in any pointer chain is the same as the key value for that node. For example, node 210 has search key 211 which is AAA. This is the same as the key value for node 210.

Each node also contains a number of pointers which point to other nodes. A node which points to another node is termed previous to the node pointed to. A node is termed subsequent to a node which points to it. The number of pointers contained by a node depends on what is termed the level of the node. The level of a particular node is assigned when the node is created. A node contains a number of pointers equal to its level plus 1. Pointers are also termed to have levels. A node of a given level contains pointers from level 0 up to the level of the node. Thus, Level 0 nodes contain one pointer, a level 0 pointer, level 1 nodes contain 2 pointers, a level 0 and a level 1 pointer, level 2 nodes contain 3 pointers, a level 0, a level 1 and a level 2 pointer, and so on.

A pointer of a given level points to the subsequent node of the same level. Thus, a level 0 pointer points to the next subsequent level 0 node, a level 1 pointer points to the next subsequent level 1 node, and so on. When a pointer of a given level is followed by a node of a greater level than the pointer, there are no nodes to which the pointer can point, so the pointer is set to 0. This means that there are no nodes of the same level as the pointer subsequent to the node. Thus, a pointer equal to 0 indicates that no nodes are subsequent to that node. This results in each node being pointed to by only one other node.

Five level 0 nodes are shown. Node 210 has pointer 212 which is 0, node 230 has pointer 232 which is 0, node 260 has pointer 262 which is 0, node 280 has pointer 282 which points to level 0 node 290 and node 290 has pointer 292 which is 0. Two level 1 nodes are shown. Node 220 has level 1 pointer 223 which is 0 and level 0 pointer 222 which points to level 0 node 230. Node 250 has level 1 pointer 253 which is 0 and level 0 pointer 252 which points to level 0 node 260. Two level 2 nodes are shown. Node 240 has level 2 pointer 244 which points to level 2 node 270, level 1 pointer 243 which points to level 1 node 250 and level 0 pointer 242 which is 0. Node 270 has level 2 pointer 274 which is 0, level 1 pointer 273 which is 0 and level 0 pointer 272 which points to level 1 node 280. Root node 201 is a level 6 node, but never contains any data.

FIG. 2b is a block diagram of an embodiment of a node 2000 of a modified SKL database structure in the database system of FIG. 1. Node 2000 includes element 2040 and pointers 2030. Element 2040 includes search key 2050 and optional data bytes 2005. Search key 2050 includes a one byte indicator of the number of compressed bytes. The bytes are removed from search key 2050 of this node because they match the search key of the previous node. Search key 2050 also includes a variable number of unique key bytes 2004. These are the bytes that are different from the search key of the previous node. Pointers 2030 always includes level zero pointer 2002. Pointers 2010 may also include higher level pointers 2010. Each pointer contains either the address of the level zero pointer of the subsequent node or zero. A pointer value of zero indicates that the node has no subsequent node of the level of the pointer. The address of a node is given by the address of it's level zero pointer. Level subscripts are negative offsets from level zero.

FIG. 3a is a flow diagram of an embodiment of read routine 120. The input parameters of routine 120 include the desired key for which the routine is to search, termed the input search parameter. Routine 120 starts in step 302, in which the root node is the current node and the highest level pointer of the root node which is in use is used to point to the next node. In step 304, the input search parameter is compared with the compressed search key of the next node. In step 306, if the input search parameter is greater then the key value, routine 120 goes to step 308, in which the next node is made the current node. Routine 120 then loops to step 304. If the input search parameter is not greater than the key value, routine 120 goes to step 310. In step 310, if the input search parameter is less than the key value, routine 120 goes to step 314. If the input search parameter is not less than the key value, the desired node has been found and routine 120 goes to step 312, in which the data field of the node is returned. Routine 120 then ends. In step 314, if routine 120 is at level 0, the desired node is not in the skip list and routine 120 goes to step 318, in which an input search parameter not found error is returned. Routine 120 then ends. If routine 120 is not at level 0, it goes to step 320, in which routine 120 moves down one level and loops to step 304.

Further description of the searching of a modified skip list data structure of the present invention may be found in the following exemplary Read Routine Program Listing A:

Further description of the comparison of an input search parameter with a search key of the present invention may be found in the following exemplary Compare Routine Program Listing B:

The compare routine returns a number less than zero if the node is less than the key, zero if the node is equal to the key, or a number greater than zero if the node is greater than the key. It also returns the number of characters successfully matched. If the node to compare with is compressed more than what was successfully matched with the previous node than the current node must also be less.

FIG. 4 is a flow diagram of replace routine 122. In Step 402, routine 122 locates the node having a search key equal to the input search parameter using a process similar to that of read routine 120, except that step 402 returns the location of the node data and routine 120 returns the node data itself. In step 404, routine 122 uses the location of the node data returned in step 402 and writes new data over the old data. Routine 122 then ends.

FIG. 5a is a flow diagram of an insert routine 124. In step 502, routine 124 locates the position for the new node by comparing the key value of the node being inserted with the key values of the existing nodes. In step 504, the identity of the node previous to the insertion point for each level in the data structure is recorded. In addition, the number of matching characters for each such node is also recorded. In step 506, the number of matching characters for the node of each level subsequent to the insertion point is recorded. In step 508, the level of the new node is calculated. In step 510, the new node is created. The search key of the new node is created by compressing and storing the number of characters of the key value removed based on the level of the new node. The pointers of the new node are created by setting the pointers of the new node to point to the subsequent nodes by copying the pointer values from the previous nodes of the same or lesser height. In step 512, the pointers of the previous nodes are adjusted to point to the new node. In step 514, the search keys of nodes subsequent to the new node are recompressed as necessary. In step 516, the level of the new node is compared to the maximum level in use in the data structure. If the new level is higher than the maximum level, routine 124 goes to step 518, in which the root node of the data structure is updated to include the new level. Routine 124 then ends. If the new level is not higher than the maximum 25 level, routine 124 ends.

Further description of the insertion of a new node in a modified skip list data structure of the present invention may be found in the following exemplary Insert Routine Program Listing C:

FIG. 5b is a flow diagram of an embodiment of the subprocess of step 508 of FIG. 5a, in which the level of the new node is calculated. The subprocess begins in step 508-1, in which the level of the new node is initially set to 0. In step 508-2, a random number is generated. In step 508-3, the random number is compared to a preselected constant p. If the random number is less than p, the subprocess goes to step 508-4, in which one is added to the level of the new node. The subprocess then goes to step 508-2. If the random number is not less than p, the subprocess goes to step 508-5, in which the resulting level of the new node is returned. The subprocess then returns to the main routine 124.

Further description of the calculation of the level of a new node in a modified skip list data structure of the present invention may be found in the following exemplary Calculate Level Routine Program Listing D:

FIG. 6 is a flow diagram of delete routine 126. In step 602, routine 126 locates the node having a search key equal to the input search parameter using a process identical to that of read routine 120, except that step 602 returns the location of the node and routine 120 returns the node data. In step 604, routine 126 uses the location of the node returned in step 602 and deletes the node by replacing each pointer which points to the node with the node's pointer of the same level. In step 606, routine 126 recompresses those keys of subsequent nodes which require recompression. Routine 126 then ends.

It is to be understood that the above described arrangement is merely illustrative of the invention and that other arrangements may be devised by those of skill in the art without departing from the spirit and scope of the invention.