Fast string searching and indexing using a search tree having a plurality of linked nodes

• US 6,047,283 A
• Filed: 02/26/1998
• Issued: 04/04/2000
• Est. Priority Date: 02/26/1998
• Status: Expired due to Term

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Braun, Bernhard
• Primary Examiner(s): Fetting, Anton W.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/031,285
• Time in Patent Office: 768 Days
• Field of Search: 707/2, 707/3, 707/1, 707/6, 707/8, 707/200, 707/202
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A fast string indexing method efficiently stores, searches, and removes alphanumeric or binary strings utilizing a compacted search tree. The number of levels in the search tree is minimized by having a node represent more than one character when possible. Each inner node of the tree contains a hash table array for successive hashing, which also minimizes the time required to traverse a given node. Searches may be performed for partial matches, such as wild cards at the character level. Multiple indices may be opened independently and concurrently on the same table of string entries.

Claims

1. A search tree for indexing a plurality of string entries, wherein each one of said plurality of string entries is a string of characters, comprising:

a plurality of linked nodes consisting of a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets.

2. The search tree for indexing a plurality of strings of claim 1, wherein the number of characters in each one of said plurality of string entries is the same.

3. The search tree for indexing a plurality of strings of claim 1, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

4. The search tree for indexing a plurality of strings of claim 1, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

5. The search tree for indexing a plurality of strings of claim 1, wherein said string of characters is a string of alphanumeric characters and at least one of said plurality of string entries contains a wildcard character.

6. The search tree for indexing a plurality of strings of claim 1, wherein a search of said search tree utilizes a LIFO memory manager for managing a stack having links to at least some of said plurality of linked nodes.

7. The search tree for indexing a plurality of strings of claim 6, wherein said search utilizes backtracking.

8. The search tree for indexing a plurality of strings of claim 6, wherein said search utilizes pruning of said stack.

9. The search tree for indexing a plurality of strings of claim 4, wherein at least some of said reference links form a doubly-linked list.

10. A method for searching for a certain string, consisting of a plurality of characters, among a plurality of strings, wherein each one of said plurality of strings is a string of characters, comprising the steps of:

creating on an R/3 system a search tree having a plurality of linked nodes consisting of a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of strings, wherein said each one of said plurality of inner nodes comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets;

forming on an R/3 system a query associated with said certain string; and

traversing said search tree utilizing said query and providing an index to any of said plurality of strings that matches said certain string.

11. A method for indexing a plurality of string entries, wherein each one of said plurality of string entries is a string of characters, comprising the steps of:

creating a search tree comprising a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets;

and applying said search tree to said indexing of said plurality of string entries.

12. The method for indexing a plurality of strings of claim 11, wherein the number of characters in each one of said plurality of string entries is the same.

13. The method for indexing a plurality of strings of claim 11, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

14. The method for indexing a plurality of strings of claim 11, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

15. The method for indexing a plurality of strings of claim 11, wherein at least some of said reference links form a doubly-linked list.

16. The method for indexing a plurality of strings of claim 11, wherein said string of characters is a string of alphanumeric characters and at least one of said plurality of string entries contains a wildcard character.

17. The method for indexing a plurality of strings of claim 11, wherein a search of said search tree utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

18. The method for indexing a plurality of strings of claim 17, wherein said search utilizes backtracking.

19. The method for indexing a plurality of strings of claim 17, wherein said search utilizes pruning of said stack.

20. A method for searching for a certain string, consisting of a plurality of characters, among a plurality of strings, wherein each one of said plurality of strings is a string of characters, comprising the steps of:

creating a search tree comprising a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets;

wherein said plurality of strings forms a plurality of string entries;

forming a query associated with said certain string; and

traversing said search tree utilizing said query and providing an index to any of said plurality of strings that matches said certain string.

21. The method for searching for a certain string of claim 20, wherein said certain string consists of a plurality of alphanumeric characters and at least one wildcard.

22. The method for searching for a certain string of claim 20, wherein said traversal utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

23. The method for searching for a certain string of claim 22, wherein said traversal utilizes backtracking.

24. The method for searching for a certain string of claim 22, wherein said traversal utilizes pruning of said stack.

25. The method for searching for a certain string of claim 20, wherein the steps of creating a search tree and forming a query associated with said certain string are performed on a human resources management, financials, logistics, business workflow, personnel management, organizational management, payroll accounting, time management, personnel development or network system.

26. A method for collision detection or collision management of requests of several users accessing a database including a first plurality of string entries, comprising maintenance of a dynamic lock table including the requests of the users, comprising the steps of:

indexing said requests as a second plurality of string entries, wherein each one of said second plurality of string entries is a string of characters, by using a search tree, said search tree comprising;

a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said second plurality of string entries, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets; and

performing a query to the lock table associated with a request of a user to the database before passing the request of the user to the database.

27. A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, cause said processor to index a plurality of string entries wherein each one of said plurality of string entries is a string of characters, by using a search tree, said search tree comprising:

a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets.

28. The computer-readable medium of claim 27, wherein the number of characters in each one of said plurality of string entries is the same.

29. The computer-readable medium of claim 27, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

30. The computer-readable medium of claim 27, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

31. The computer-readable medium of claim 27, wherein at least some of said reference links form a doubly-linked list.

32. The computer-readable medium of claim 27, wherein said string of characters is a string of alphanumeric characters and at least one of said plurality of string entries contains a wildcard character.

33. The computer-readable medium of claim 27, wherein a search of said search tree utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

34. The computer-readable medium of claim 33, wherein said search utilizes backtracking.

35. The computer-readable medium of claim 33, wherein said search utilizes pruning of said stack.

36. A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, causes said processor to search for a certain string, consisting of a plurality of characters, among a plurality of strings, wherein each one of said plurality of strings is a string of characters, comprising the steps of:

creating a search tree comprising a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of string entries, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets;

wherein said plurality of strings forms a plurality of string entries;

forming a query associated with said certain string; and

traversing said search tree utilizing said query and providing an index to any of said plurality of strings that matches said certain string.

37. The computer-readable medium of claim 36, wherein said certain string consists of a plurality of alphanumeric characters and at least one wildcard.

38. The computer-readable medium of claim 36, wherein said traversal utilizes a last-in first-out memory manager for managing a stack having links to at least some of said plurality of linked nodes.

39. The computer-readable medium of claim 36, wherein said traversal utilizes backtracking.

40. The computer-readable medium of claim 36, wherein said traversal utilizes pruning of said stack.

41. The computer-readable medium of claim 36, wherein the steps of creating a search tree and forming a query associated with said certain string are performed on a human resources management, financials, logistics, business workflow, personnel management, organizational management, payroll accounting, time management, personnel development or network system.

42. A computer-readable medium having stored thereon a plurality of instructions, said plurality of instructions including instructions which, when executed by a processor, cause said processor to detect or manage a collision of requests of several users accessing a database including a first plurality of string entries, by:

maintaining a dynamic lock table including requests of the users;

indexing said requests as a second plurality of string entries, wherein each one of said second plurality of string entries is a string of characters, by using a search tree, said search tree comprising;

a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said second plurality of string entries, wherein said each one of said plurality of inner nodes further comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets; and

performing a query to the lock table associated with a request of a user to the database before passing the request of the user to the database.

43. A system for searching a certain string, consisting of a plurality of characters, among a plurality of strings, wherein each one of said plurality of strings is a string of characters, comprising:

means for creating a search tree having a plurality of linked nodes comprising a root node, a plurality of inner nodes wherein each one of said plurality of inner nodes is associated with a character or substring of characters, and a plurality of leaf nodes associated with said plurality of strings, wherein said each one of said plurality of inner nodes comprises;

(a) a reference to a parent node, wherein said parent node is either said root node or another of said plurality of inner nodes;

(b) a first data field containing a character comparison position indicating the number of characters in said character or substring of characters associated with said one of said plurality of inner nodes;

(c) a second data field containing a comparison character, said comparison character used to determine whether said character or substring of characters associated with said one of said plurality of inner nodes is contained in a string entry at a character position of said string entry associated with said character comparison position;

(d) a reference to at least two successor nodes; and

(e) a hash table array containing a predetermined number of hash buckets;

means for submitting a query associated with said certain string; and

tree traversal means for providing an index to any of said plurality of strings that matches said certain string.

44. The system of claim 43, wherein the number of characters in each one of said plurality of strings is the same.

45. The system of claim 43, wherein at least one of said plurality of inner nodes has a reference to a parent node having a character comparison position that is at least two less than the character comparison position of said at least one of said plurality of inner nodes.

46. The system of claim 43, wherein each one of said plurality of inner nodes is associated with a level and further comprises a reference link to at least one of said plurality of linked nodes also associated with said level.

47. The system of claim 43, wherein said certain string consists of a plurality of alphanumeric characters and at least one wildcard.

48. The system of claim 43, comprising collision detection or collision management by use of a dynamic lock table.