Skip to content

Indexed Vectors

Jump to bottom
James Courtney edited this page Sep 14, 2021 · 5 revisions

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 act like a Dictionary.

Sample

[FlatBufferTable]
public class Person
{
    // It is recommended to make 'Key' properties immutable. Take a look at the immutability
    // page for more details.
    [FlatBufferItem(0, Key = true)]    
    public virtual string Name { get; init; }

    [FlatBufferItem(1)]    
    public virtual PhoneNumber PhoneNumber { get; set; }
}

[FlatBufferTable]
public class PhoneBook
{
    // The key type here must be string because the 'Name' property in 'Person' is a string.
    [FlatBufferItem(0)]
    public virtual IIndexedVector<string, Person> Contacts { get; init; }
}

public void CreatePhonebook()
{
   var phoneBook = new PhoneBook { Contacts = new IndexedVector<string, Person>() };

   // The initial phone book uses a dictionary under the hood to implement IIndexedVector.
   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];
   FlatBufferSerializer.Default.Serialize(phoneBook, buffer);
   
   // The deserialized phone book uses binary search under the hood to implement IIndexedVector.
   var parsedBook = FlatBufferSerializer.Default.Parse<PhoneBook>(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));
}

FBS Sample

Indexed Vectors can also be defined in FBS files:

namespace Foo;

attribute "fs_setter";
attribute "fs_vector";

table Person 
{ 
    Name:string (key, fs_setter:"PublicInit"); // generate init-only setter for immutability
    PhoneNumber:string;
}

table PhoneBook 
{ 
    Contacts:[Person] (fs_vector:"IIndexedVector"); 
}

Indexed Vector Limitations

Nothing is free and Indexed Vectors too have some limitations:

  1. The generic Key type must match the Key Property. In this example, the 'Name' property is a string, so the Indexed Vector Key type is also a string. You'll get a runtime exception if this isn't defined correctly.
  2. Indexed Vector keys are limited to the same types as regular FlatBuffer sorted vector keys, which is to say strings and scalars.
  3. 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.
  4. A FlatBuffer Table can only have one property with the 'Key' attribute defined, so it isn't possible to index on multiple fields.

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.

Further Reading

Clone this wiki locally