Page Comparison

1. Indexing Survey

Refer Trees Survey

2. Memory Allocation

...

We need to allocate to b+ tree nodes in the master server. B+ tree is represented by B+ tree nodes linked with pointers. A general structure of a B+ tree node is as follows:

...

struct node {
int key;
int primary_key; // only for leaf node
int left_child_key; // index table key
int right_child_key; // index table key
}

Issues:

• Maintaining Index table during splits
• Storing the root node key (for global access)

...

• Table Manager:
  • The new table manager needs to store the index information.
  • Index: TableId + IndexId + IndexKey -> Index ServerId
  • Logical representation of index is a tree.
  • Internally represented as an ordered list of siblings where each sibling contains StartKeyHash.
  • Index Types: signed int8, signed int32, signed int64, string, float
  • comparison function: implied by types

• Object Finder
  • tableId + primaryKeyHash -> tableServer
  • tableId + indexId + indexKey -> IndexServer
  • master: to find index partitions, and to find its own data

• RPCs for schema mgmt management from client to coordinator
  • createIndexRPC( tableId, indexType, indexId, serverSpan)
    • serverSpan=0 -> to be placed on the same server as the table
  • dropIndexRPC( tableId, indexId) 

• RPCs for schema mgmt management from coordinator to mastersmaster
  • takeTabletOwnership()
  • dropTabletOwnership()
  • takeIndexOwnership()
  • dropIndexOwnership()
  • notifyIndexChange(): invoked from create index rpc or during re-partitioning

• RPCs for schema information from coordinator to client (for lookups)
  • getTabletMap()
  • getTabletConfig()