Patent ID: 6643653
Filing Date: 2003-11-04
Classification: G06F

Abstract:
A method of mapping a key sequence of data to a target sequence of data, if the target sequence is stored in a computer readable memory, the method comprising:retrieving, from a root node of the computer readable memory corresponding to the value of a first datum in said key sequence, an identifier of a first block; for one or more blocks starting with said first block, wherein each of said blocks is one of a virtual block comprising one or more nodes and a leaf configured to store a sequence of data: determining whether said block is a virtual block or a leaf; if said block is a virtual block: locating a node in said virtual block corresponding to the value of a next datum in said key sequence; retrieving a home block identifier from said node; and if said home block identifier identifies said virtual block, accessing a next block identified by a next block identifier of said node; and if said block is a leaf: determining whether said leaf contains said target sequence of data; if said leaf contains said target sequence of data, retrieving said target sequence; if said leaf does not contain said target sequence, accessing a next block identified by a next block identifier of said leaf if said leaf contains a next block identifier.