System and methodology for providing compact B-Tree

• US 6,694,323 B2
• Filed: 01/27/2003
• Issued: 02/17/2004
• Est. Priority Date: 04/25/2002
• Status: Active Grant

• Current Assignee: iAnywhere Solutions Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Bumbulis, Peter
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US10/352,465
• Publication Number:
  US 20030204513A1
• Time in Patent Office: 386 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/101, 707/102, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An improved method for creating an index based on a path-compressed binary trie in a database system comprising database tables and indexes on those tables is described. For a given index to be created, a path-compressed binary trie for the given index is determined. The path-compressed binary trie comprises internal nodes and leaf nodes. Based on a traversal of the path-compressed binary trie, an index is created comprising a first array of internal nodes encountered during the traversal, and a second array of leaf nodes encountered during the traversal. The database system employs said first and second arrays for providing index-based access for a given key value.

Claims

1. In a database system comprising database tables and indexes on those tables, an improved method for creating an index based on a path-compressed binary trie, the method comprising:

for a given index to be created, determining a path-compressed binary trie for the given index, said path-compressed binary trie comprising internal nodes and leaf nodes;

based on a traversal of said path-compressed binary trie, creating an index comprising;

a first array of internal nodes encountered during the traversal, and

a second array of leaf nodes encountered during the traversal; and

wherein said system employs said first and second arrays for providing index-based access for a given key value.

2. The method of claim 1, wherein each particular internal node includes a bit offset indicating a particular bit value of the given key value to be examined at the particular internal node during traversal of the index.

3. The method of claim 2, wherein said bit offset represents a relative bit position.

4. The method of claim 2, wherein said bit offset represents an absolute bit position.

5. The method of claim 1, wherein traversal of said path-compressed binary trie includes pre-order traversal of said path-compressed binary trie.

6. The method of claim 1, wherein traversal of said path-compressed binary trie includes post-order traversal of said path-compressed binary trie.

7. The method of claim 1, wherein said determined path-compressed binary trie comprises a tree-based data structure, wherein each particular internal node points to at least two subtrees, and wherein each particular internal node stores information indicating a size for at least one of its subtrees.

8. The method of claim 7, wherein each particular internal node also stores information indicating which particular subtree is having its size tracked by the node.

9. The method of claim 8, wherein the particular subtree is identified as being a selected one of a left subtree and a right subtree.

10. The method of claim 7, further comprising:

receiving a request to search the index based on a particular key value;

while traversing the first array, using said information about subtree size to skip internal nodes in the first array that can be excluded, based on key value, from the search of the index.

11. The method of claim 1, further comprising:

receiving a request to search the index based on a given key value;

traversing internal nodes in the first array to locate a particular leaf which may contain said given key value;

comparing said given key value to a key value at the particular leaf.

12. The method of claim 11, further comprising:

if said given key value does not match the key value at the particular leaf, locating the position of a leaf containing a value matching said given key value based, at least in part, on the first bit at which said given key value and the key value at the particular leaf differ.

13. The method of claim 1, further comprising:

receiving a request to insert a given key value into the index;

traversing internal nodes in the first array to locate a particular leaf in the second array for insertion of said given key value;

comparing said given key value to a key value at the particular leaf; and

determining a position for insertion said given key value based, at least in part, on the first bit at which said given key value and the key value at the particular leaf differ; and

inserting said given key value at the determined position and adjusting nodes in the first array and second array based upon insertion of said given key value.

14. The method of claim 1, further comprising:

receiving a request to delete a particular key value;

traversing internal nodes in the first array to locate said particular key value in the second array; and

adjusting nodes in the first array and second array based upon deletion of said particular key value.

15. The method of claim 1, wherein said determined path-compressed binary trie comprises a tree-based structure in which each leaf node contains key values and each internal node includes a bit offset and has two child subtrees.

16. The method of claim 15, wherein said bit offset at a given internal node indicates a bit value of a particular key value to be examined to determine a direction to take at the internal node in traversing the path-compressed binary tree to locate said particular key value.

17. The method of claim 1, wherein correspondence between internal nodes in the first array and corresponding leaf nodes in the second array may be determined based on each node'"'"'s respective array position.

18. The method of claim 1, wherein said first array includes bit offsets in the order encountered in a pre-order traversal of said path-compressed binary trie.

19. The method of claim 1, wherein said first array includes bit offsets in the order encountered in a post-order traversal of said path-compressed binary trie.

20. The method of claim 1, wherein said determined path-compressed binary trie comprises a tree-based data structure, wherein each particular internal node stores information indicating a size for at least one of its subtrees and a bit offset indicating a bit value to be examined to determine a direction to take in traversing the tree-based data structure to locate a given key value.

21. The method of claim 1, wherein a selected one of a search operation, an insert operation, a delete operation, a split operation, and a merge operation may be performed directly on said first array and said second array.

22. The method of claim 1, wherein said second array includes a pointer to a key value for each leaf node.

23. The method of claim 1, wherein said first array comprises an encoding of said determined path-compressed binary trie structure.

24. The method of claim 1, wherein said second array comprises an ordered array of leaf nodes of said path-compressed binary trie.

25. The method of claim 1, further comprising:

for each leaf node, storing in said second array an indicator as to whether the next key value is equal to the key value of the current leaf node.

26. A computer-readable medium having processor-executable instructions for performing the method of claim 1.

27. A downloadable set of processor-executable instructions for performing the method of claim 1.

28. In a database system, said database system storing a plurality of data records, an improved method for creating a path-compressed binary trie index of such records, the method comprising:

adding key values from at least some of the data records to at least one index page;

for each index page, determining a path-compressed binary trie of key values in said index page, said path compressed binary trie including leaf nodes and non-leaf nodes;

traversing said path-compressed binary trie and creating a path-compressed binary trie index by performing the substeps of;

for each non-leaf node of said path-compressed binary trie, storing in a first array a bit offset and information about size of at least one subtree of said each non-leaf node, said bit offset indicating a particular bit value of the given key value to be examined at the non-leaf node during traversal of the index; and

for each leaf node of said path-compressed binary trie, storing in a second array a pointer to a key value.

29. The method of claim 28, wherein said index pages comprise B-tree index pages.

30. The method of claim 28, wherein said index pages comprise B+-tree index pages.

31. The method of claim 28, further comprising:

for each leaf node, storing in said second array an indicator as to whether the next key value is equal to the key value of the current leaf node.

32. The method of claim 28, further comprising:

for each index page, storing a header block in addition to said first array and said second array.

33. The method of claim 28, wherein said key values are stored on child pages for non-leaf index pages.

34. The method of claim 28, wherein said key values are obtained from the data records for leaf index pages.

35. The method of claim 28, further comprising:

for each index page, storing a value based on a count of a selected one of leaf nodes, internal nodes, and all nodes on the index page.

36. The method of claim 28, further comprising:

for at least some index pages, storing a key value for the index page, said key value associated with a pointer to the index page in the parent of the index page.

37. The method of claim 28, further comprising:

sorting said key values before creating said path-compressed binary trie index.

38. The method of claim 28, further comprising:

determining whether to create a selected one of a B-Tree index and a path-compressed binary trie index for a particular set of data records.

39. The method of claim 38, wherein said determining step includes evaluating the width of the column being indexed.

40. The method of claim 38, wherein said determining step includes evaluating the length of the key values.

41. The method of claim 28, wherein said bit offset represents a relative bit position.

42. The method of claim 28, wherein said bit offset represents an absolute bit position.

43. The method of claim 28, wherein said determined path-compressed binary trie comprises a tree-based data structure, wherein each particular non-leaf node points to at least two subtrees.

44. The method of claim 28, wherein each particular internal node also stores information indicating which particular subtree is having its size tracked by the node.

45. The method of claim 44, wherein the particular subtree is identified as being a selected one of a left subtree and a right subtree.

46. The method of claim 28, further comprising:

receiving a request to search the index based on a particular key value while searching pages during index traversal,

while traversing the first array, using said information about subtree size to skip non-leaf nodes in the first array that can be excluded, based on key value, from the search of the index.

47. The method of claim 28, wherein correspondence between non-leaf nodes in the first array and corresponding leaf nodes in the second array may be determined based on each node'"'"'s respective array position.

48. The method of claim 28, wherein said step of storing said pointer in a second array includes storing a key value on child pages for non-leaf index pages.

49. The method of claim 28, further comprising:

normalizing said key values to binary strings in an order preserving fashion.

50. The method of claim 28, wherein said pointers to key values comprise data record identifiers for leaf index pages.

51. The method of claim 28, wherein a selected one of a search operation, an insert operation, a delete operation, a split operation, and a merge operation may be performed directly on said index pages without reconstructing said path-compressed binary trie.

52. The method of claim 28, further comprising:

for each leaf node, storing an indicator in said first array as to whether the key value associated with the next leaf node is equal to the key value of the current leaf node.

53. The method of claim 28, wherein said step of adding key values includes linking a particular index page to its parent page and allocating a new index page when said particular index page is full.

54. The method of claim 53, wherein said step of linking said particular index page includes adding an entry for said particular index page in its parent page.

55. The method of claim 28, further comprising:

appending a row identifier to said key values in the event key values are not unique.

56. The method of claim 28, wherein said step of traversing said path-compressed binary trie includes a pre-order traversal.

57. The method of claim 28, wherein said step of traversing said path-compressed binary trie includes a post-order traversal.

58. A computer-readable medium having computer-executable instructions for performing the method of claim 28.

59. A downloadable set of computer-executable instructions for performing the method of claim 28.