Uploaded image for project: 'Blazegraph (by SYSTAP)'
  1. Blazegraph (by SYSTAP)
  2. BLZG-641 Improve load performance
  3. BLZG-376

Adjust B+Tree leaf split points to chose shorter separator keys.

    XMLWordPrintable

    Details

    • Type: Sub-task
    • Status: Open
    • Resolution: Unresolved
    • Affects Version/s: TERMS_REFACTOR_BRANCH
    • Fix Version/s: None
    • Component/s: B+Tree
    • Labels:
      None

      Description

      When a B+Tree leaf is split, a separator key is lifted into the parent node which is the shortest prefix of the last key in the left sibling and the first key in the right sibling. However, it is often possible to select a shorter separator key by splitting the leaf to the right or left of the center. Separator keys lifted into a node a propagated up the B+Tree, so finding a better separator will sometimes result in a significant space savings. The actual savings depends on the length of the keys in the leaves and their distribution.

      A related technique to improve storage utilization is to defer leaf splits by rotating keys among siblings until 2 leaves are full, at which point they are split. This yeilds 3 leaves which are 2/3rds full rather than 2 leaves which are 1/2 full. However, bigdata uses exact fit records on the WORM and index segments and best fit records on the RWStore, so the space savings from this approach will be less drammatic than for a database which targets a fixed size page.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              bryanthompson bryanthompson
              Reporter:
              bryanthompson bryanthompson
              Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

                Dates

                Created:
                Updated: