Multi-level directory tree with fixed superblock and block sizes for select operations on bit vectors

1. A method comprising: accessing a bit vector having a bit vector length; generating, using the bit vector, a data structure including: a first level of superblocks including large superblocks and small superblocks; a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks; a third level of sub-blocks, each sub-block associated with a block; and the large superblocks each have a length greater than a first constant that is independent of the bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length; storing the data structure; executing a select operation on the bit vector, the select operation operating on the bit vector, data indicative of a bit-type, and an occurrence value, the select operation returning an index of an occurrence of the bit-type in the bit vector that equals occurrence value wherein the occurrence of the bit-type characterizes a number of times the bit-type occurs within a sequence of bits characterized by the bit vector, the bit vector characterizing a text document the execution of the select operation utilizing the data structure and performed as part of a text query; wherein blocks associated with large superblocks characterize explicit local large superblock indexes of the bit-type of the bit vector, blocks associated with small superblocks characterize locations of sub-blocks, the sub-blocks associated with the large blocks characterize explicit local large block indexes of the bit-type of the bit vector, and sub-blocks associated with small blocks characterize a cumulative number of occurring bit-types in a portion of the bit vector; and wherein a number of bits within the large superblocks is greater than a number of bits within the small superblocks.

2. The method of claim 1 , wherein the first level of superblocks is represented as at least a first level array storing a location of a predetermined occurrence of a bit-type in the bit vector, the second level of blocks is represented as at least a plurality of second level arrays, and the third level of sub-blocks is represented as at least a plurality of third level arrays.

3. The method of claim 1 , wherein generating the data structure includes:

determining a boundary of each superblock in the bit vector as a predetermined occurrence of the bit-type in the bit vector;

determining whether each superblock is large or small based on whether a given superblock has a length greater than the first constant that is independent of the bit vector length;

storing explicit indexes of the bit-type of each large superblock in each associated block;

determining a boundary of each block associated with a small superblock in the bit vector;

determining whether each block associated with the small superblocks is large or small based on whether a given block has a length greater than the second constant that is independent of the bit vector length;

storing explicit indexes of the bit-type of each large block in each associated sub-block; and

storing, in each respective sub-block associated with each respective large block, a cumulative number of occurring bit-types in an associated portion of the bit vector.

4. The method of claim 3 , wherein the predetermined occurrence of the bit-type in the bit vector defining the boundary of each superblock is 2 12 , the first constant that is independent of the bit vector length is equal to 2 20 , and the second constant that is independent of the bit vector length is equal to 2 14 .

5. The method of claim 1 , wherein the bit-type is a 0 bit or a 1 bit, and wherein the bit vector is an array of 0 and 1 bits.

6. The method of claim 1 , wherein at least one of the accessing, the generating, and the storing is performed by at least one data processor forming part of at least one computing system.

7. A method comprising: receiving data characterizing a bit vector and a bit-select value; executing a select operation on the bit vector by at least searching a data structure for an index of a bit-select value occurrence of a bit-type in the bit vector, the select operation operating on a bit vector, data indicative of the bit-type, and the bit-select value occurrence, the select operation returning the index of the bit-select value occurrence of the bit-type in the bit vector that equals the bit-select value occurrence, wherein the bit-select value occurrence of the bit-type characterizes a number of times the bit-type occurs within a sequence of bits characterized by the bit vector, the bit vector characterizing a text document, the searching utilizing the data structure and performed as part of a text query, the data structure including: a first level of superblocks including large superblocks and small superblocks; a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks; a third level of sub-blocks, each sub-block associated with a block; the large superblocks each have a length greater than a first constant that is independent of a bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length; and providing the index of the bit-select value occurrence of the bit-type; wherein blocks associated with large superblocks characterize explicit local large superblock indexes of the bit-type of the bit vector, blocks associated with small superblocks characterize locations of sub-blocks, the sub-blocks associated with the large blocks characterize explicit local large block indexes of the bit-type of the bit vector, and sub-blocks associated with small blocks characterize a cumulative number of occurring bit-types in a portion of the bit vector; and wherein a number of bits within the large superblocks is greater than a number of bits within the small superblocks.

8. The method of claim 7 , wherein the first level of superblocks is represented as at least a first level array storing a location of a predetermined occurrence of the bit-type in the bit vector, the second level of blocks is represented as at least a plurality of second level arrays, and the third level of sub-blocks is represented as at least a plurality of third level arrays.

9. The method of claim 8 , wherein the searching includes:

determining if the bit-select value is contained in the first level array;

determining, using the first level array, a superblock having the bit-select value occurrence of the bit-type;

determining one of the plurality of second level arrays associated with the determined superblock;

determining if the bit-select value is contained in the determined one of the plurality of second level arrays;

determining one of the plurality of the third level arrays associated with the determined second level array having the bit-select value occurrence of the bit-type; and

determining an index of the bit-select value occurrence of the bit-type from the determined one of the plurality of the third level arrays.

10. The method of claim 7 , wherein a bit-select operation is performed during a text search engine operation.

11. The method of claim 7 , wherein at least one of the receiving, the searching, and the providing is performed by at least one data processor forming part of at least one computing system.

12. A system comprising: at least one data processor; and memory storing instructions, which when executed by the at least one data processor, implement operations comprising: receiving data characterizing a bit vector and a bit-select value, executing a select operation on the bit vector by at least searching a data structure for an index of a bit-select value occurrence of a bit-type in the bit vector, the select operation operating on a bit vector, data indicative of the bit-type, and the bit-select value occurrence, the select operation returning the index of the bit-select value occurrence of the bit-type in the bit vector that equals the hit-select value occurrence, wherein the bit-select value occurrence of the bit-type characterizes a number of times the bit-type occurs within a sequence of bits characterized by the bit vector, the bit vector characterizing a text document, the searching utilizing the data structure and performed as part of a text query, the data structure including: a first level of superblocks including, large superblocks and small superblocks; a second level of blocks including large blocks and small blocks, each block associated with one of the superblocks; a third level of sub-blocks, each sub-block associated with a block; the large superblocks each have a length greater than a first constant that is independent of a bit vector length and the large blocks each have a length greater than a second constant that is independent of the bit vector length; and providing the index of the bit-select value occurrence of the bit-type; wherein blocks associated with large superblocks characterize explicit local large superblock indexes of the bit-type of the bit vector, blocks associated with small superblocks characterize locations of sub-blocks, the sub-blocks associated with the large blocks characterize explicit local large block indexes of the bit-type of the bit vector, and sub-blocks associated with small blocks characterize a cumulative number of occurring bit-types in a portion of the bit vector; and wherein a number of bits within the large superblocks is greater than a number of bits within the small superblocks.

13. The system of claim 12 , wherein the first level of superblocks is represented as at least a first level array storing a location of a predetermined occurrence of the bit-type in the bit vector, the second level of blocks is represented as at least a plurality of second level arrays, and the third level of sub-blocks is represented as at least a plurality of third level arrays.

14. The system of claim 13 , wherein the searching includes:

determining if the bit-select value is contained in the first level array;

determining, using the first level array, a superblock having the bit-select value occurrence of the bit-type;

determining one of the plurality of second level arrays associated with the determined superblock;

determining if the bit-select value is contained in the determined one of the plurality of second level arrays;

determining one of the plurality of the third level arrays associated with the determined second level array having the bit-select value occurrence of the bit-type; and

determining an index of the bit-select value occurrence of the bit-type from the determined one of the plurality of the third level arrays.

15. The system of claim 12 , wherein a bit-select operation is performed during a text search engine operation.

16. The method of claim 1 , wherein generating the data structure includes:

determining a boundary of each superblock in the bit vector as a predetermined occurrence of a bit-type in the bit vector;

determining whether each superblock is large or small based on whether a given superblock has a length greater than the first constant that is independent of the bit vector length;

storing explicit indexes of the bit-type of each large superblock in each associated block;

determining a boundary of each block associated with a small superblock in the bit vector;

determining whether each block associated with the small superblocks is large or small based on whether a given block has a length greater than the second constant that is independent of the bit vector length;

storing explicit indexes of the bit-type of each large block in each associated sub-block; and

storing, in each respective sub-block associated with each respective large block, a cumulative number of occurring bit-types in an associated portion of the bit vector; and

wherein a bit-type is a 0 bit or a 1 bit, and wherein the bit vector is an array of 0 and 1 bits.

17. The method of claim 1 , wherein the select operation is executing as part of a text search query by a text search engine forming part of an enterprise database system executing queries on database tables.

18. The method of claim 1 , wherein a time to execute the select operation is independent of the bit-vector length.

19. The method of claim 1 , wherein a time to execute the select operation does not increase with an increase in the bit vector length.