Parallel bottom-up construction of radix trees

Abstract

A method for partitioning keys onto radix tree logical pages and a parallel index page build algorithm in order to provide radix tree build speedup proportional to the number of processors on the system and controlled efficient page utilization. Also, since keys are intelligently partitioned so that a complete set of keys is inserted into a logical page, there is no page overflow during the tree construction and thus page splitting is eliminated. Since radix index trees are really groups of logical pages in which each logical page contains a small tree, the tree is built (with respect to the logical pages) from the bottom up, while within each individual logical page the tree is constructed from the top down. The space required for a logical page is pre-allocated to allow construction of limbs to begin without waiting for the build of their underlying pages to complete.

Claims

What is claimed is:

1. A method for building a radix tree, comprising the computer executed steps of:

allocating pages in said radix tree, wherein said pages are organized into levels from a leaf level at the bottom of said radix tree to a trunk level at the top of said radix tree;

partitioning keys into said pages at each level of said radix tree starting at said leaf level of said radix tree and progressing to said trunk level of said radix tree, wherein all subtrees of keys on a first page have a common parent on said first page; and

building each page by inserting said keys into said page starting at the top of said page and progressing to the bottom of said page.

2. The method of claim 1, wherein said partitioning step further comprises:

assigning a text of difference s core (TOD) score to each key entry;

scanning said keys searching for a decline in said TOD score between successive keys; and

partitioning said keys into said groups of pages based on said decline in said TOD score.

3. The method of claim 1, wherein each page in said building step is built in parallel on multiple processors.

4. An apparatus for building a radix tree, comprising:

means for allocating pages in said radix tree, wherein said pages are organized into levels from a leaf level at the bottom of said radix tree to a trunk level at the top of said radix tree;

means for partitioning keys into said pages at each level of said radix tree starting at said leaf level of said radix tree and progressing to said trunk level of said radix tree, wherein all subtrees of keys on a first page have a common parent on said first page; and

means for building each page by inserting said keys into said page starting at the top of said page and progressing to the bottom of said page.

5. The apparatus of claim 4, where in said partitioning means further comprises:

means for assigning a text of difference score (TOD) score to each key entry;

means for scanning said keys searching for a decline in said TOD score between successive keys; and

means for partitioning said keys into said groups of pages based on said decline in said TOD score.

6. The apparatus of claim 4, wherein each page in said building means is built in parallel on multiple processors.

7. A program product for building a radix tree, comprising:

means for allocating pages in said radix tree, wherein said pages are organized into levels from a leaf level at the bottom of said radix tree to a trunk level at the top of said radix tree;

means for partitioning keys into said pages at each level of said radix tree starting at said leaf level of said radix tree and progressing to said trunk level of said radix tree, and wherein all subtrees of keys on a first page have a common parent on said first page;

means for building each page by inserting keys into said page starting at the top of said page and progressing to the bottom of said page;

signal-bearing media bearing said allocating means, said partitioning means, and said building means.

8. The program product of claim 7, wherein said partitioning means further comprises:

means for assigning a text of difference score (TOD) score to each key entry;

means for scanning said keys searching for a decline in said TOD score between said successive keys; and

means for partitioning said keys into groups of pages based on said decline in said TOD score.

9. The program product of claim 7, wherein each page in said building means is built in parallel on multiple processors.

Description

FIELD OF THE INVENTION

This invention relates to the data structure of radix trees. More particularly, this invention relates to the parallel construction from the bottom up of a radix tree.

BACKGROUND

A database is an amalgamation of data that has an organized structure in the memory of a computer system. Data in a database can be organized via a tree (also called an index), which is a data structure that defines the organization of data in memory in such a way so as to allow for fast searching of the data and dynamic sorting (also called collating) of the data. A database can be comprised of data spaces that contain records and indexes that define how the records can be accessed by the computer system. A record contains keys, which are the contents of the record that identify the record and which are capable of being searched for and sorted on. An index provides a logical ordered list of its associated records based on key values in the records. An index can be used by the computer system to provide a sorted order for the tree to facilitate fast searching of the tree for a record that has a particular key.

The tree data structure takes its name from the trees of nature because they both have a branching relationship between nodes. A tree data structure is divided (also called partitioned) into logical memory pages, which are blocks of data paged as a unit between primary and secondary storage in a computer system. In partitioning a tree, the goal is to minimize the amount of data that must be paged to locate a particular key, thus increasing system performance. The trunk page is the first, or topmost, logical page of a tree. The leaf pages are the bottom-most logical pages in the tree. The limb pages are logical pages between the leaf pages and the trunk page. Thus, the tree data structure grows downward from the top, the opposite of trees in nature.

A radix tree is a type of tree that uses bit tests to determine the path to a key. Instead of comparing the whole search key with the various index entries, in a binary radix tree a single bit of the search key is tested on each step through the tree and, thereby, it is determined which of two paths will be followed on the next step. Similarly, in a quad-radix tree, two bits of the search key is tested on each step through the tree and, thereby, it is determined which of four paths would be followed on the next step. By extension, radix trees with a multiplicity of paths can be supported.

Certain bits of the search key are not tested in a radix tree because all of the candidates (those index entries which have satisfied all the prior tests) have those bits in the same state. Radix trees have front end compression in that leading text common among two or more successive keys is stored only once in the tree, usually on a non-leaf tree page. Radix trees are powerful data structures because they allow similar searching performance as do B-trees but with significantly less space utilization. However, an efficient radix tree build mechanism that can take advantage of parallel processing does not exist.

Computers with multiple, parallel processors capable of operating independently in order to provide a performance advantage are becoming prevalent. In a parallel processing computer system, work is broken up into independent pieces, which are executed concurrently (that is, in parallel) by multiple processors. Thus, just as 10 ditch diggers working concurrently can theoretically dig a ditch 10 times faster than a single ditch digger, 10 processors working in parallel can theoretically perform a piece of work 10 times faster than a single processor. However, in order to realize this theoretical maximum performance speed up, the work being divided into pieces must be independent and not have sequential requirements, that is each piece must be capable of being executed without regard to and without waiting for the outcome of all other pieces.

In the prior art, a radix tree is constructed from the top down by sequentially traversing the keys and inserting them into the tree, so as to provide a sorted order by key for the records in the tree. This sequential, serial build process does not lend itself to being broken up in parallel operations for execution on multiple, parallel processors. Thus, the prior art index construction is not capable of taking advantage of the potential benefits of parallel processing and does not allow for a performance speed up proportional to the number of processors in the computer system.

In the prior art, partitioning of the tree into logical pages is done on a dynamic basis as the tree grows. Consequently, during the process of tree construction as keys, are inserted into the tree, an insertion of a key onto a full logical page would cause the logical page on which it is inserted to overflow and split into two pages. This splitting of a page can increase the index tree depth unless the residue from the split (i.e., the data on the new parent of the split-off child pages) is merged into its parent page. (The index tree depth is the number of pages that a search algorithm must visit in order to find a key of interest. A search algorithm of a tree with a large index depth will thus experience many page faults and resulting poor performance). This merge may, in turn, cause overflow on the parent page and it may be required to split that page and merge the residue into its parent page, the grandparent page of the original split page. This extra paging activity could potentially undulate up to the trunk page and is a significant performance degradation in the prior art top-down radix tree build method because pages must be repeatedly revisited and processed.

In an attempt to solve this problem, some prior art solutions have attempted to achieve less paging at build time by reducing the number of logical page splits by using lower page utilizations, e.g. 50% of the page initially has data to allow for future expansion. This solution suffers from the problem of increased index depth and increased paging at runtime with a corresponding degradation in runtime performance. There is increased paging at runtime because there are more pages since each page has less data.

The ability to build a radix tree from the bottom up instead of from the top down would solve the above undulation problem because page splits become unnecessary since the keys for each index page are known before construction of the page begins. Knowing the keys assigned to each logical page in advance would also result in decreased index depth and better page utilization, ultimately resulting in improved performance.

Bottom-up build methods require knowledge of exactly which keys will be deposited on a given index partition (logical page). Since the contents of each index partition must be known prior to actually building the partition, page splits are eliminated, page utilization can be rigidly controlled, and if multiple partitions are constructed simultaneously, a speed up proportional to the number of processors can be achieved.

However, radix trees have two characteristics that complicate the task of determining exactly what data belongs in each index partition. These characteristics must be accounted for in order to build a radix tree from the bottom-up.

First, radix trees have front end compression in that leading text common among two or more successive keys is stored only once in the tree, usually on a non-leaf tree page. Common text must be taken into consideration when grouping key data since it directly affects page utilization. Common text must be positioned prior to any keys in the tree for which it is common. Thus, common text must be stripped from current keys and counted as space utilization for prior pages.

Second, the node structure of a radix tree is fixed depending on the key data in the tree. All keys in a radix tree partition must be in the same node-structure subtree (i.e., all subtrees on a page must have a common parent on that page) and thus cannot be arbitrarily grouped to satisfy page utilization or reference concerns.

Both of these characteristics must be accommodated in order to produce a functionally correct radix tree, but the prior art has not been able to accommodate these characteristics without actually building the tree top-down and analyzing the resultant tree structure.

For the foregoing reasons, there is a need for a method that detects which keys can functionally be placed together on radix tree index pages, to facilitate bottom up parallel construction of the tree, which would be a significantly better performer than building the tree from the top down.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide an enhanced index build mechanism.

It is a further object to provide for parallel construction from the bottom up of an index, which would provide a performance gain proportional to the number of processors used in parallel.

It is a further object to provide parallel construction from the bottom up of a radix tree.

It is a further object to provide an enhanced index build mechanism of a radix tree that eliminates page splitting and gives controlled efficient page utilization.

These and other objects are achieved by a fast method for partitioning keys onto radix tree logical pages and a parallel index page build algorithm in order to provide radix tree build speedup proportional to the number of processors on the system and controlled efficient page utilization. Also, since keys are intelligently partitioned so that a complete set of keys is inserted into a logical page, there is no page overflow during the tree construction and thus page splitting is eliminated. Since, in the preferred embodiment, radix index trees are really groups of logical pages in which each logical page contains a small tree, the tree is built (with respect to the logical pages) from the bottom up, while within each individual logical page the tree is constructed from the top down. The space required for a logical page is pre-allocated to allow construction of limbs to begin without waiting for the build of their underlying pages to complete.

To build a radix tree from the bottom up in parallel, the list of sorted keys contained in the tree is divided into groups of keys that are eligible to be deposited on a logical page and multiple logical pages are constructed simultaneously. The three factors that determine which keys can be deposited on a logical page are: the common text shared by two consecutive keys in the index, the bit-of-difference value between consecutive keys in the index, and the logical page size used in the tree.

Logical pages of the tree are built in parallel given that the key text to be placed on those pages does not contain any common text that should be placed on prior levels of the tree (e.g., higher level common text must be stripped from the keys before insertion).

The bit-of-difference value is the bit position (starting from 0) in which two hexadecimal representations of two characters in two successive sorted keys in the index are different.

Logical pages of an index tree are packed as close to the desired page utilization range as possible.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a block diagram of a computer system, according to the preferred embodiment.

FIG. 2 is a data calculation diagram that shows how the text of difference score is computed, according to the preferred embodiment.

FIG. 3 shows an example of a binary radix tree data structure, according to the preferred embodiment.

FIG. 4 shows the resulting partitioned binary radix tree data structure, according to the preferred embodiment.

FIGS. 5 and 6 are flow charts that describe the operation of the control program as it does a parallel index build, according to the preferred embodiment.

FIG. 7 is block diagram of an article of manufacture or a computer program product including a storage medium for storing thereon program means for carrying out the control program, according to the preferred embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The preferred embodiment provides a fast method for partitioning keys onto radix tree logical pages and a parallel index page build mechanism in order to provide radix tree build speedup proportional to the number of processors on a computer system and controlled efficient page utilization. Also, since keys are intelligently partitioned so that a complete set of keys is inserted into a logical page, there is no page overflow during the tree construction and thus page splitting is eliminated. A complete set of keys occurs when all subtrees on the same page have a common parent on that page. Since, in the preferred embodiment, radix index trees are really groups of logical pages in which each logical page contains a small tree, the tree is built (with respect to the logical pages) from the bottom up, while within each individual logical page the tree is constructed from the top down.

The preferred embodiment does not wait for all pages at the same level to complete before requesting the build of parent limbs; instead, as soon as all pages under a limb are requested, page construction can begin for that parent limb. Although the requests to construct the pages are generated one level at a time, the processing that constructs the page can run simultaneously so that the actual page construction is not limited to one level.

To build a radix tree from the bottom up in parallel, the list of sorted keys contained in the tree is divided into groups of keys that are eligible to be deposited on a logical page and multiple logical pages are constructed simultaneously. The three factors that determine which keys can be deposited on a logical page are: the common text shared by two consecutive keys in the index, the bit-of-difference value between consecutive keys in the index, and the logical page size used in the tree.

Logical pages of the tree are built in parallel given that the key text to be placed on those pages does not contain any common text that should be placed on prior levels of the tree (e.g., higher level common text must be stripped from the keys before insertion).

The bit-of-difference value is the bit position (starting from 0) in which two hexadecimal representations of two characters in two successive sorted keys in the index are different.

Logical pages of an index tree are packed as close to the desired page utilization range as possible.

FIG. 1 shows a block diagram of computer system 100, according to a preferred embodiment. Computer system 100 contains multiple processors 102 connected via bus 120 to storage 104 and memory 106.

Memory 106 is a random access memory sufficiently large to hold the necessary programming and data structures. While memory 106 is shown as a single entity, it should be understood that memory 106 may in fact comprise a plurality of modules, and that memory may exist at multiple levels, from high-speed registers and caches to lower speed but larger DRAM chips. Memory 106 contains control program 107, key list 114, and radix tree 112. Control program 107 is further divided into client task 108 and multiple server tasks 110, which both contain instructions that, when executed on processors 102, carry out the preferred embodiment as further described under the description for FIGS. 5 and 6. The contents of memory 106 can be loaded from and stored to storage 104 as processors 102 have a need for it.

In the preferred embodiment, storage 104 is DASD (Direct Access Storage Device), although it could also be other storage such as floppy disk drives, tape drives, removable memory cards, or optical storage. While storage 104 is depicted as a single entity, it should be understood that storage 104 may in fact comprise a plurality of storage devices.

In the preferred embodiment, computer system 100 is an IBM AS/400.TM.. Computer system 100 could also be another type of computer system, whether it be another microcomputer such as a PS/2.TM. or an Apple Macintosh.TM., or a mainframe computer such as an IBM System/390.TM., and still fall within the spirit and scope of this invention. In addition, computer system 100 could be a microcomputer such as described above but connected to a larger computer system such as an IBM AS/400.TM.. It will be readily appreciated that the principles of the invention may apply to other computer applications, such as other mainframes, minicomputers, network servers, supercomputers, personal computers, or workstations. Therefore, while the discussion herein focuses on a particular IBM AS/400.TM. application, the invention should not be limited to the particular hardware or software designs, performance parameters, or application-specific functions disclosed herein.

Client task 108 creates key list 114, which contains all keys 118 in tree 112 sorted in ascending order. Client task 108 then partitions groups of keys from key list 114 to place at the leaf level of tree 112. The criteria for selecting partitions (groups) of keys is described below under the description for FIGS. 5 and 6. If there is leading text common to all keys in the group and any adjacent group or key, the client task strips the common text from each key in the group since the common text is stored in the tree at a position common to both groups. For each group (partition) of keys formed, client task 108 then allocates a page (storage) and sends a leaf page construction request to a server task's queue, and adds an entry replacing the selected keys to key list 114. The updated key list 114, containing both new entries representing the groups selected and keys not selected, forms a new list which will be used later for building the prior (parent) logical limb level. Keys not selected for a group remain in key list 114 in the same order as they are on key list 114 being processed so that sorted ascending order of the keys in key list 114 is maintained.

When client task 108 reaches the end of key list 118, all page construction requests for that level have been sent to server task 110 and key list 118 has been updated to reflect the groups at the leaf level. The client task continues partitioning keys for each level of tree 112 until the trunk page is reached. The operation of client task 108 in the preferred embodiment is more fully described in the flowchart of FIG. 6.

Multiple server tasks 110, capable of executing in parallel on multiple processors 102, process logical page construction requests, received from client task 108 concurrently and separately. Upon receiving a request, server task 110 builds an index subtree top-down for the given set of keys, as is further described below under the description for FIG. 6. Then, server task 110 sends a response to the client's response queue. Top-down subtree construction is the act of performing standard key insertion for each key in the given key set. The operation of server task 110 in the preferred embodiment is more fully described in the flowcharts of FIGS. 5 and 6.

Client task 108 partitions the keys (i.e. divides the list of sorted keys into groups of keys, as described above) at each tree level based on three criteria: leading common text, bit-of-difference value between adjacent keys, and the key text size. The first two criteria provide valid split points but the last one ultimately determines if a key can be put into a logical page. Client task 108 accomplishes both the leading common text criteria and the bit-of-difference criteria by assigning a value of "8" to each leading text key byte in common between two keys. Client task 108 adds this value to the bit-of-difference value (0 through 7) to give a final text-of-difference (TOD 116) score between 2 consecutive keys, as shown by the following formula:

text.sub.-- of.sub.-- difference.sub.-- score=(8*number.sub.-- of.sub.-- leading.sub.-- bytes.sub.-- in.sub.-- common)+bit.sub.-- of.sub.-- difference.sub.-- value.

Given an ascending list of keys, the client task uses the following four rules to partition the keys:

1. Only consecutive keys are grouped together.

2. Adjacent keys are grouped in the order of text-of-difference score. In other words, an entity (a key or a group) must be grouped with an adjacent key with a higher TOD score before it can be grouped with another adjacent key with a lower TOD.

3. Entries with common text can be split across pages provided that leading common text is properly removed and used for the prior limb level.

4. All proper key groupings are subtrees in the radix tree node structure.

Based on the above rules, the client task groups a list of keys by assigning a TOD value to each key entry. (TOD value is defined as the value between that entry and its preceding entry.) Then the client task scans the list from start to end looking for split points. A decline in TOD value indicates this is a proper split point where two preceding entities can be grouped to form a new entity (partition) with a resulting TOD being the lowest TOD value of the entities in the group. An exception to this split point is where the TOD declines from first entry to the second entry. In this case, since there is no entry prior to the first entry, no grouping is done.

The grouping process is continued until a fall page is detected or all keys are processed. At this point, all pending groups are sent off for logical page construction. For the full page condition, the list is virtually truncated at that point and the process is continued forward at the next entry.

FIG. 2 shows an example of how TOD is calculated for two adjacent keys, "BAA" and "BARK". Bytes one and two containing the characters "B" and "A" are common leading text in these two keys. Thus they have two bytes in common. These two keys first differ in the third bit of the third byte. Thus, TOD is 8*2+3=19.

To illustrate how key list 114 could be partitioned for parallel logical page construction, consider the example of the binary radix tree structure depicted in FIG. 3. For the sake of simple illustration, real key text is used instead of pointer to a key structure. The keys 118 used for the construction of the tree structure of FIG. 3 are as shown in Table 1.

                  TABLE 1
    ______________________________________
                ARF
                BAA
                BARK
                CHEEP
                CHIRP
                CRY
                GROWL
                HOOT
                HOWL
                MEOW
                MOO
                PEEP
                PLOP
                QUACK
                ROAR
                SQUAWK
                SQUEAK
                SQUEAL
                TWEET
                TWITTER
                WHINNEY
    ______________________________________

                  TABLE 2
    ______________________________________
    TOD                 Key
    ______________________________________
    0                   ARF
    6                   BAA
    19                  BARK
    7                   CHEEP
    20                  CHIRP
    11                  CRY
    5                   GROWL
    4                   HOOT
    18                  HOWL
    3                   MEOW
    11                  MOO
    6                   PEEP
    11                  PLOP
    4                   QUACK
    7                   ROAR
    2                   SQUAWK
    29                  SQUEAK
    47                  SQUEAL
    7                   TWEET
    21                  TWITTER
    5                   WHINNEY
    ______________________________________

                  TABLE 3
    ______________________________________
    TOD               Key
    ______________________________________
    0                 ARF
    6                 (BAA BARK)
    7                 CHEEP
    20                CHIRP
    11                CRY
    5                 GROWL
    ______________________________________

                  TABLE 4
    ______________________________________
    TOD               Key
    ______________________________________
    0                 ARF
    6                 (BAA BARK)
    7                 (CHEEP CHIRP)
    11                CRY
    5                 GROWL
    4                 HOOT
    18                HOWL
    3                 MEOW
    ______________________________________

                  TABLE 5
    ______________________________________
    TOD                 Key
    ______________________________________
    5                   GROWL
    4                   HOOT
    18                  HOWL
    3                   MEOW
    ______________________________________

                  TABLE 6
    ______________________________________
    TOD               Key
    ______________________________________
    5                 GROWL
    4                 (HOOT HOWL)
    3                 MEOW
    ______________________________________

                  TABLE 7
    ______________________________________
    Logical Page Address
                        Key
    ______________________________________
    p1                  BAA BARK
    p2                  HEEP HIRP
    p3                  HOOT HOWL
    p4                  MEOW MOO
    p5                  PEEP PLOP
    p6                  QUACK ROAR
    p7                  EAK EAL
    p8                  TWEET TWITTER
    ______________________________________

                  TABLE 8
    ______________________________________
    TOD                 Key
    ______________________________________
    0                   ARF
    6                   p1
    7                   C-p2
    11                  CRY
    5                   GROWL
    4                   p3
    3                   p4
    6                   p5
    4                   p6
    2                   SQUAWK
    29                  SQU-p7
    7                   p8
    5                   WHINNEY
    ______________________________________

                  TABLE 9
    ______________________________________
    TOD                 Key
    ______________________________________
    0                   ARF
    6                   p1
    7                   (C-p2 CRY)
    5                   GROWL
    4                   p3
    ______________________________________

                  TABLE 10
    ______________________________________
    TOD                Key
    ______________________________________
    0                  ARF
    6                  (p1 C-p2 CRY)
    5                  GROWL
    4                  p3
    ______________________________________

                  TABLE 11
    ______________________________________
    TOD              Key
    ______________________________________
    0                (ARF p1 C-p2 CRY)
    5                GROWL
    4                p3
    3                p4
    ______________________________________

                  TABLE 12
    ______________________________________
    TOD           Key
    ______________________________________
    0             (ARF p1 C-p2 CRY GROWL)
    4             p3
    3             p4
    ______________________________________

                  TABLE 13
    ______________________________________
    TOD           Key
    ______________________________________
    0             (ARF p1 C-p2 CRY GROWL p3)
    3             p4
    6             p5
    4             p6
    2             SQUAWK
    ______________________________________

                  TABLE 14
    ______________________________________
    TOD           Key
    ______________________________________
    0             (ARF p1 C-p2 CRY GROWL p3)
    3             (p4 p5)
    4             p6
    2             SQUAWK
    ______________________________________

                  TABLE 15
    ______________________________________
    TOD           Key
    ______________________________________
    0             (ARF p1 C-p2 CRY GROWL p3)
    3             (p4 p5 p6)
    2             SQUAWK
    . . .
    ______________________________________

                  TABLE 16
    ______________________________________
            ARF p1 C-p2 CRY GROWL p3
            p4 p5 p6
            SQUAWK SQU-p7 p8 WHINNEY
    ______________________________________

                  TABLE 17
    ______________________________________
    0                    p9
    3                    p10
    2                    p11
    ______________________________________

    ______________________________________
    Main --
    /* Process the key list from start to end. Group keys into partitions.
    */
    /* For each partition, send off a request for logical leaf page
    construction. */
    /* Also, build another list for next prior limb level processing. */
    Call build.sub.-- a.sub.-- level;
    Do while not reaching trunk level
    /* Now a new list for prior limb level has already been created. */
    /* Proeess the list from start to end. Group entries into partitions. */
    /* For each partition, allocate a page and send off a request to build
    a limb page.*/
    /* Build another list for prior level processing. */
    Call build.sub.-- a.sub.-- level;
    End;      /* end do while
                           */
    /* Wait for all logical page construction requests to be completed. */
    end;      /* main      */
    procedure build.sub.-- a.sub.-- level
    build.sub.-- a.sub.-- level:proc;
    /* Initialization */
    last.sub.-- point := 1;
    n :=1;
    /* Rolling forward to find a proper split point so that preceding
    consecutive keys could be combined to form a group */
    Do while (n <= #.sub.-- of.sub.-- keys.sub.-- in.sub.-- list)
    If /* there is an increase in the score between consecutive keys or this
    is the first processing entry */ (score{n} < score{n+1 }) (n =
    last.sub.-- point)
    then
    ;/* No decision can be made. Keep on rolling forward */
    else /* Since this is the greatest score from the last starting point,
    this
    is the proper split point for a group's upper bound. It's proper to
    combine Nth key with its preceding entity. However, that can be done
    only if the new group could be fitted onto a logical page. */
    If (key n and preceding entity would not fit on a logical.page) /* This
    implies that preceding entity is a group since at least 2 entries must
    be
    fitted on a given logical page. Also, this is a proper spot for a new
    starting point. */
    then
    Send off current group(s) for processing;
    /* There could be more than one groups pending for
    expansion. */
    For each group formed, create and add an entry to the new list;
    Copy any entry not selected (from the last starting point) to
    the new list for next level processing;
    /* Remember that all entries up to this point have been
    processed */
    last.sub.-- point := n + 1;
    else /* key n and the preceding entity could be fitted onto a logical
    page */
    Group Nth key with its preceding entity;
    Mark the Nth key and its preceding entity to indicate that they
    are already selected/acquired into a partition;
    Update left.sub.-- bound accordingly if preceding entity is a key;
    /* Now we need to expand this new group by acquiring either its
    preceding entity or succeeding key. The adjacent entity with a
    higher score will be the candidate for acquisition */
    spin.sub.-- back := on;
    Roll backward up to the last processing point to find the proper
    split point;
    Set left.sub.-- bound to the entry preceding the first entry of current
    group;
    Do while not passing last processing point and page is not full
    and backward score is > forward score
    (left.sub.-- bound > last.sub.-- point) until (spin.sub.-- back=off);
    If TOD between first entry of the group and its preceding
    entity is higher than TOD between last entry of the group
    and its succeeding entity (score{left.sub.-- bound+1} >
    score{n+1}) then
            /* this is not a split point */
            /* It's proper to combine the preceding entity into the
            group. However, that could be done only if the new
            group could be fiffed onto a logical page. */
            If preceding entity and current group could be fitted
            onto a logical page then
              Group preceding entity with current group;
              If necessary, mark entries to indicate that they are
              already selected/acquired into a partition;
              Update left.sub.-- bound (index to previous entry) to
              continue rolling backward;
              If preceding entity is a group then
                Skip other entries (if any) already
                acquired to this group and directly get to
                the entry prior to the first entry of the
                current group;
              else
                Roll back one more entry left.sub.-- bound :=
                left.sub.-- bound - 1;
            else /* preceding entity and current group would not fit
            onto a logical page. It implies this is a valid split point
            */
              Send off current group(s) for processing;
              For each group formed, create and add an entry
              to the new list;
              Copy entries not selected to the new list;
              /* Remember this is the last processing point so
              that is point will not be passed when rolling
              backward later */
              last.sub.-- point := n +1;
              /* Stop rolling backward
              spin.sub.-- back := off;
    else
            /* Stop rolling backward. */
            spin.sub.-- back := off;
    end;            /* rolling backward */
    /* Continue rolling forward
    n := n + 1;
    End;            /* rolling forward */
    n := n - 1;
    /*  Process any remaining entries and group. */
    /* For each group formed, create and add an entry to the new list. */
    /* Copy entries not selected to the new list. */
    end;          /* procedure build.sub.-- a.sub.-- level */
    ______________________________________

• Inventors
  Bui, Thuan Quang; Helt, Scott Dennis; Iyer, Balakrishna Raghavendra; Ricard, Gary Ross;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Oct-20-1998
• Current US Classes:
  370/408
  707/2
  707/7
  711/1
• Application #
  621757
• International Classes
  G06F 017/30
• Field of Search
  395/607 395/602 395/182.13 707/7 707/2 711/1 370/408
• Examiner
  Black; Thomas G.
• Agent
  Gamon; Owen J.
• US Patent References:
  4774657
  4819156
  5058002
  5179699
  5202986
  5241648
  5345585
  5355473
  5446887
  5490258
  5546390
  5659728