56 Dynamic B+Tree type information

Type information in B+Tree nodes

It is a requirement that IPersistable objects have registered serialisation and deserialisation methods. In particular this must be the case for the B+Tree nodes. That raises questions how how type information is recorded in the nodes.

The B+Tree nodes serialise TypeInfo for the key and mapped value types.

When a cref<LeafNode> is dereferenced, Serialise() is called to deserialise it, and this includes an array of keys. Therefore Serialise() must have access to the type of the keys. There are 4 options:

  1. The type of the key is implicit in the type of the LeafNode - so we will need to register many LeafNode classes.
  2. The type of the key is recorded in the LeafNode (before it deserialises the keys) using a TypeOpsId. This is mapped to a TypeOps. The TypeOps is then used to deserialise the keys.
  3. In the scope where the xmap is accessed, TLS is used to set the type for the key and payload.
  4. Use slots in the archive for holding TypeOps of key and payload.

We reject the 1st approach because it

  • makes it too difficult for scripting languages to define xmaps, since there is a need to generate a specialisation of a LeafNode.
  • makes it more difficult to allow C++ programmers to simply declare xmaps as they need them and they work without any additional declarations.
  • makes it more difficult to avoid bloat

The 3rd approach has the advantage of

  • avoiding the space overhead of persistent type information
  • avoiding the CPU overload of mapping a type identifier to a TypeOps
  • avoiding the need for all the complicated registries

However there are problems with the 3rd and 4th approaches:

  • When the PersistStore asynchronously deletes a tree TLS won't be set
  • When VisitObjects is called by the GC TLS won't be set. Therefore it won't be possible to visit into keys and payloads.

TypeOpsId

Currently cxPersistStore defines TypeOpsId and this is recorded in the B+Tree nodes to identify the key and value data types. TypeOpsId is an index into a table in the PersistStore. 

$typedef+ ssize_t TypeOpsId;

BTreeTypeInfo.h

Source: Ceda/cxPersistStore/src/dynamic_bplustree/BTreeTypeInfo.h