Method and system for managing an index arrangement for a directory

• US 7,822,736 B2
• Filed: 09/28/2006
• Issued: 10/26/2010
• Est. Priority Date: 09/30/2005
• Status: Expired due to Fees

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Ramsay, Ronald W., Harvey, Richard H.
• Primary Examiner(s): Le; Uyen T.
• Application Number:
  US11/536,276
• Publication Number:
  US 20070078888A1
• Time in Patent Office: 1,489 Days
• Field of Search: None
• US Class Current: 707/711
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

According to one embodiment of the invention, a method for managing an index arrangement for a directory includes storing a plurality of data values from the directory in an alternate evaluator. The alternate evaluator includes a processor operable to process a directory operation. The method also includes generating a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size. The method further includes storing a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored in the alternate evaluator.

Claims

1. A method for processing directory operations, comprising:

retrieving a plurality of data values from a directory;

storing the plurality of data values in electronic memory;

generating a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size;

storing a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored;

receiving a directory operation;

deciding whether to evaluate the directory operation using an evaluator;

in response to deciding not to evaluate the directory operation using the evaluator, evaluating the directory operation by passing the directory operation through one or more processing layers in a data path; and

in response to deciding to evaluate the directory operation using the evaluator, evaluating the directory operation based on stored data values in the index using the evaluator.

2. The method of claim 1, wherein the first value in the at least one page comprises a syntax normalized value.

3. The method of claim 1, further comprising:

storing a counter in the at least one page, wherein the counter is indicative of a total number of pointers in the page; and

resizing the page based on the counter.

4. The method of claim 1, further comprising generating a second index, the second index comprising at least one page, the at least one page comprising one or more pointers from the second index to the first index.

5. The method of claim 4, further comprising adding a second level to the second index.

6. The method of claim 4, further comprising balancing the second index to increase the occupancy ratio of the second index by organizing the second index to provide a particular number of pointers at each page.

7. The method of claim 4, further comprising sorting the second index to support a binary search algorithm.

8. The method of claim 4, further comprising storing the second index as a B-tree.

9. A system for processing directory operations, comprising:

a processor; and

a storage device embodying a program of instructions operable, when executed on the processor, to;

retrieve a plurality of data values from a directory;

store the plurality of data values in electronic memory;

generate a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size;

store a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored;

receive a directory operation;

decide whether to evaluate the directory operation using an evaluator;

in response to deciding not to evaluate the directory operation using the evaluator, evaluate the directory operation by passing the directory operation through one or more processing layers in a data path; and

in response to deciding to evaluate the directory operation using the evaluator, evaluate the directory operation based on stored data values in the index using the evaluator.

10. The system of claim 9, wherein the first value in the at least one page comprises a syntax normalized value.

11. The system of claim 9, wherein the program of instructions is further operable to:

store a counter in the at least one page, wherein the counter is indicative of a total number of pointers in the page; and

resize the page based on the counter.

12. The system of claim 9, wherein the program of instructions is further operable to generate a second index, the second index comprising at least one page, the at least one page comprising one or more pointers from the second index to the first index.

13. The system of claim 12, wherein the program of instructions is further operable to add a second level to the second index.

14. The system of claim 12, wherein the program of instructions is further operable to balance the second index to increase the occupancy ratio of the second index by organizing the second index to provide a particular number of pointers at each page.

15. The system of claim 12, wherein the program of instructions is further operable to sort the second index to support a binary search algorithm.

16. The system of claim 12, wherein the program of instructions is further operable to store the second index as a B-tree.

17. Logic encoded in tangible media, the logic being operable, when executed on a processor, to:

retrieve a plurality of data values from a directory;

store the plurality of data values in electronic memory;

generate a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size;

store a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored;

receive a directory operation;

decide whether to evaluate the directory operation using an evaluator;

in response to deciding not to evaluate the directory operation using the evaluator, evaluate the directory operation by passing the directory operation through one or more processing layers in a data path; and

in response to deciding to evaluate the directory operation using the evaluator, evaluate the directory operation based on stored data values in the index using the evaluator.

18. The logic of claim 17, wherein the first value in the at least one page comprises a syntax normalized value.

19. The logic of claim 17, wherein the logic is further operable to:

store a counter in the at least one page, wherein the counter is indicative of a total number of pointers in the page; and

resize the page based on the counter.

20. The logic of claim 17, wherein the logic is further operable to generate a second index, the second index comprising at least one page, the at least one page comprising one or more pointers from the second index to the first index.

21. The logic of claim 20, wherein the logic is further operable to add a second level to the second index.

22. The logic of claim 20, wherein the logic is further operable to balance the second index to increase the occupancy ratio of the second index by organizing the second index to provide a particular number of pointers at each page.

23. The logic of claim 20, wherein the logic is further operable to sort the second index to support a binary search algorithm.

24. The logic of claim 20, wherein the logic is further operable to store the second index as a B-tree.