Apache Ignite: How does the indexing work?

Question

How does Apache Ignite's indexing work? I haven't found those technical details in the documentation.

1. Is it using a B-tree?
2. Where is the index stored?
3. How is it stored?
4. What performance (in Big-O notation) does the index provide after build in usage?
5. How fast does it build, when does it build?
6. Ignite can store arbitrary serializable Java objects. How does it deal with composites when I want to index a field of a sub-sub-object?
7. Ignite Cache is a key-value store. Am I able to have different classes (=types as objects) as values? In other words, is Ignite Cache Schemaless? If yes, how does this fit with my SQL-queries?
8. Ignite Cache is a key-values store. How does do the keys come into play if I SQL-query for my values? What am I querying for?
9. The keys can be arbitrary, serializable Java objects - am I able to query for the keys or only the values?

Answer 1

This information is not covered really much in docs because it is mostly implementation detail and can change from version to version. After all the source code is available if you are interested in details. To be specific I'm talking about Ignite 1.5 which is about to be released.

1. Before 1.5 the default data structure was a snap-tree (variant of avl-tree), since 1.5 skip-list option was added as well and it is a default now.
2. In java heap or in off-heap memory depending on config.
3. Reliably :) I don't understand this question.
4. log(N) on update and lookup.
5. Index is getting updated on each transaction commit (or just cache update in case of atomic cache), there is no separate build phase. You can expect you indexes to be in correct state after each update.
6. Ignite has two options (since 1.5): either to store objects in binary format which allows to get separate field values or keep the whole object deserialized and use reflection.
7. etc.

Have fun!