Memory efficient lookup structure

1. A method comprising:

utilizing, by a computing device, a first array of data lookup entries and a second array of a plurality of metadata entries for maintaining an ordering among the data lookup entries in the first array using a tree structure, each of the metadata entries being associated with a corresponding level of a plurality of levels and storing:

a first data index value identifying a data lookup entry in the first array;

a first metadata index value identifying a metadata entry in a same level of the tree structure; and

a second metadata index identifying a metadata entry in a level below the corresponding level of the tree structure;

locating a data lookup entry in the first array, the data lookup entry corresponding to a lookup value, associated with a received request, from among the data lookup entries in the first array; and

processing the request in response to locating the lookup value among the data lookup entries in the first array.

2. The method of claim 1 , wherein:

processing the request comprises translating a first address in a first address space to a second address in a second address space using the located data lookup entry.

3. The method of claim 2 , wherein the first address is located within a range of addresses in the first address space identified by the located data lookup entry.

4. The method of claim 1 , further comprising:

updating the tree structure to add a new data lookup entry to the tree structure while maintaining the ordering among the data lookup entries in the first array.

5. The method of claim 4 , wherein updating the tree structure comprises rebalancing the tree structure.

6. The method of claim 1 , wherein each of the metadata entries in a lowest level of the plurality of levels has a same position in the second array as a corresponding data lookup entry in the first array.

7. The method of claim 1 , wherein a number of metadata entries is between a first predetermined number and a second predetermined number.

8. The method of claim 6 , wherein the lowest level is a leaf level.

9. The method of claim 1 , further comprising, maintaining a list of data entries deleted from the tree structure.

10. A non-transitory machine readable medium having stored thereon instructions for performing a method comprising machine executable code which when executed by at least one machine, causes the machine to:

utilize a first array of lookup nodes and a second array of a plurality of metadata nodes for maintaining an ordering among the lookup nodes in the first array using a multi-level structure, each of the metadata nodes being associated with a corresponding level of a plurality of levels and storing:

a first data index pointing to a position of a lookup node in the first array;

a first metadata index pointing to a position of a metadata node in a same level of the multi-level structure; and

a second metadata index pointing to a position of a metadata node in a level below the corresponding level of the multi-level structure;

locate a lookup node in the first array, the lookup node corresponding to a lookup value, associated with a received data transaction, from among the lookup nodes in the first array; and

process the data transaction in response to locating the lookup value among the lookup nodes in the first array.

11. The non-transitory machine readable medium of claim 10 , wherein:

to process the data transaction, the machine translates a first address in a first address space to a second address in a second address space using the located lookup node.

12. The non-transitory machine readable medium of claim 11 , wherein the first address is located within a range of addresses in the first address space identified by the located lookup node.

13. The non-transitory machine readable medium of claim 10 , the machine further:

updates the multi-level structure to add a new lookup node to the multi-level structure while maintaining the ordering among the lookup nodes in the first array.

14. The non-transitory machine readable medium of claim 13 , wherein updating the multi-level structure comprises rebalancing the multi-level structure.

15. The non-transitory machine readable medium of claim 10 , wherein each of the metadata nodes in a lowest level of the plurality of levels has a same position in the second array as a corresponding one of the lookup nodes in the first array.

16. The non-transitory machine readable medium of claim 15 , wherein a number of first metadata nodes is between a first predetermined number and a second predetermined number.

17. A computing device comprising:

a memory containing machine readable medium comprising machine executable code having stored thereon instructions for performing a method of processing requests; and a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:

utilize a first array of data lookup entries and a second array of metadata entries for maintaining an ordering among the data lookup entries in the first array using a tree structure, each of the metadata entries being associated with a corresponding level of a plurality of levels and storing a first data index value identifying a data lookup entry by its position in the first array, a first metadata index value identifying a metadata entry in a same level of the tree structure by its position in the second array, and a second metadata index value identifying a metadata entry in a level below the corresponding level of the tree structure by its position in the second array;

locate a data lookup entry in the first array, the data lookup entry corresponding to a lookup value, associated with a received request, from among the data lookup entries; and

process the request in response to locating the lookup value among the data lookup entries.

18. The computing device of claim 17 , wherein:

to process the request the processor translates a first address in a first address space to a second address in a second address space using the located data lookup entry; and

the first address is located within a range of addresses in the first address space identified by the located data lookup entry.

19. The computing device of claim 17 , wherein the processor is further caused to:

update the tree structure to add a new data lookup entry to the tree structure while maintaining the ordering among the data lookup entries in the first array.

20. The computing device of claim 19 , wherein to update the tree structure the processor rebalances the tree structure.