Indexed Vectors - jamescourtney/FlatSharp GitHub Wiki

FlatBuffers does not currently support dictionaries (hash tables). FlatSharp's philosophy is to avoid extending FlatBuffers in ways that might break compatibility in the future.

In lieu of Dictionaries, FlatBuffers does support Sorted Vectors. Sorted Vectors sort data when serializing, which means that Binary Search can be used to look up items in log(n) time after deserializing. However, this is only true of deserialized items. The real issue with sorted vectors is the programming model:

 // no indication on whether it is sorted or not, so binary search may work or it may not.
IList<MyTable> vector = myBuffer.Vector;
vector.BinarySearch("foo");

Indexed Vectors

FlatSharp solves this problems with a concept called Indexed Vectors, which are declared with the IIndexedVector<TKey, TValue> interface. Indexed Vectors look like a Dictionary, and sometimes even are a Dictionary.

Sample

table Person
{ 
    // It is recommended to make 'Key' properties immutable and required. Take a look at the immutability
    // page for more details.
    name : string (key, required, fs_setter:"PublicInit");

    phone_number : string;
}

table PhoneBook (fs_serializer:"Lazy")
{
    contacts : [ Person ] (fs_vector:"IIndexedVector");
}

Using this schema looks like:

public void CreatePhonebook()
{
   // The initial phone book uses a dictionary under the hood to implement IIndexedVector.
   var phoneBook = new PhoneBook { Contacts = new IndexedVector<string, Person>() };

   phoneBook.Contacts.Add(new Person { Name = "Michael", PhoneNumber = "1" });
   phoneBook.Contacts.Add(new Person { Name = "Gob", PhoneNumber = "2" });
   phoneBook.Contacts.Add(new Person { Name = "Buster", PhoneNumber = "3" });
   phoneBook.Contacts.Add(new Person { Name = "Lindsay", PhoneNumber = "4" });

   byte[] buffer = new byte[1024];
   PhoneBook.Serializer.Write(buffer, phoneBook);
   
   // The deserialized phone book uses binary search under the hood to implement IIndexedVector.
   var parsedBook = PhoneBook.Serializer.Parse(buffer);
   Assert.IsTrue(phoneBook.Contacts.TryGetValue("Michael", out var michael));
   Assert.IsTrue(phoneBook.Contacts.TryGetValue("Gob", out var gob));
   Assert.IsTrue(phoneBook.Contacts.TryGetValue("Lindsay", out var lindsay));
   Assert.IsTrue(phoneBook.Contacts.TryGetValue("buster", out var buster));
   Assert.IsTrue(phoneBook.Contacts.TryGetValue("Michael", out var michael));
}

Indexed Vector Limitations

Nothing is free and Indexed Vectors too have some limitations:

  1. Indexed Vector keys are limited to the same types as regular FlatBuffer sorted vector keys, which is to say strings and scalars.
  2. Indexed Vectors can't add arbitrary key/value pairs. They take an instance of the value type and infer the key from that, which is why Keys should be immutable as a best practice. See the Defining Immutable Objects page for guidance about creating immutable fields and tables.
  3. A FlatBuffer Table can only have one property with the 'Key' attribute defined, so it isn't possible to index on multiple fields.
  4. Indexed Vectors don't support lookup for duplicate keys. While the underlying sorted vector may have repeated keys (this is not illegal), using Indexed Vectors in FlatSharp will make some of these keys unaddressable. For Indexed Vectors created within FlatSharp, duplicate keys are disallowed to avoid this. However, when interoping with other languages, keep this in mind.

Cross-Language Support

From a FlatBuffer perspective, Indexed Vectors are just regular Sorted Vectors. So it's possible to use Indexed Vectors in C# with FlatSharp, and sorted vectors with other languages subject to the caveats above.

Further Reading

⚠️ **GitHub.com Fallback** ⚠️