How to store array index (an integer) as keys in a B+tree?

Question

I have looked at every example of a B+tree in JavaScript on GitHub, and have tried simplifying one down to semi-readable code from this. But I still don't understand what the structure of the keys array is for each internal node. What do the keys look like? How do you use them in the get/insert/remove algorithms? Specifically for this question, I want to treat the B+tree as an array from the outside, or a list of sorts. So I want the "key" to be an integer (the index of the item in the array). How do I do this? What is an example JSON demo showing what a simple B+tree will look like in this case?

{
  type: 'tree',
  keys: [?],
  children: [
    {
      type: 'internal',
      keys: [?],
      children: [
        {
          type: 'leaf',
          value: { foo: '123' }
        },
        {
          type: 'leaf',
          value: { foo: '234' }
        }
      ]
    },
    {
      type: 'internal',
      keys: [?],
      children: [
        {
          type: 'leaf',
          value: { foo: '345' }
        },
        {
          type: 'leaf',
          value: { foo: '456' }
        }
      ]
    }
  ]
}

What do the keys do even? I get they are used for lookup, somehow, but how?

Say there are 32 internal nodes from the base, and each of those have 32 internal nodes, and each of those have a bunch of leaves. What are the keys in the internal nodes?

I want to implement a robust B+tree in JavaScript, and am having a hard time understanding the basics of the B+tree at this moment.

score 0 · Accepted Answer · answered Jan 06 '21 at 22:28

So I want the "key" to be an integer (the index of the item in the array). How do I do this?

No, you can't use the absolute index of the item in the whole structure as the key. That would mean when inserting/deleting at the front of your array, all nodes in the entire tree would need to have their indices updated.

Instead, you need to store the sizes of the subtrees, so that you can accumulate them into relative indices when traversing the tree - you've done this in How to return the tree node by index when tree nodes have subtree size? already. These sizes never change unless the node itself (or one of its children) change, so you will always have to update only O(log n) nodes.

What is an example JSON demo showing what a simple B+tree will look like in this case?

{ type: 'internal',
  // size: 8,
  // childSizes: [2, 3, 3],
  keys: [2, 5],
  children: [
    { type: 'leaf',
      // size: 2
      // childSizes: [1, 1]
      keys: [1],
      values: [ {…}, {…} ]
    },
    { type: 'leaf',
      // size: 3,
      // childSizes: [1, 1, 1],
      keys: [1, 2],
      values: [ {…}, {…}, {…} ]
    },
    { type: 'internal',
      // size: 3
      // childSizes: [1, 2]
      keys: [1],
      chilren: [
        { type: 'leaf',
          // size: 1
          // childSizes: [1]
          keys: [],
          values: [ {…} ]
        },
        { type: 'leaf',
          // size: 2
          // childSizes: [1, 1]
          keys: [1],
          values: [ {…}, {…} ]
        },
      ]
    },
  ]
}

It would be enough if each node had only its size in a field, but that would require loading all children of a node into memory only for the accumulation of sizes to find which child to choose in a lookup/insert/delete operation, so it's usually not done. You might store the node sizes in their parent nodes (as childSizes) instead. Or you might already store the accumulated sizes in that keys array of the B+ tree, so that you don't need to compute the sums during search (but then will have to update the entire array if only one entry changes - it's a tradeoff). Unlike a classical B+ tree which only stores the k-1 "boundary" keys between the k children, it would probably be a good idea to store the complete sum (= the size of the node) in the last array index.

How to store array index (an integer) as keys in a B+tree?

1 Answers1