Labels & Indexes

Labels group nodes/edges. Used for:

• Type filtering: MATCH (p:Person) vs all nodes.
• Indexes: per-label per-property indexes.
• Constraints: uniqueness on Person.email.

Implementation:

• Each node has a bitmap of label IDs.
• Per-label list: Person -> [node_id_1, node_id_5, node_id_99, ...].
• Scanning all Persons = walk that list.

Per-property indexes:

• B-tree, hash, or LSM index per (label, property).
• MATCH (p:Person {email: '[email protected]'}) → index lookup.

Composite indexes: (label, prop1, prop2).

Full-text indexes: tokenize string properties for CONTAINS/STARTS_WITH queries. Backed by Lucene in Neo4j.

Schema-on-write vs schema-on-read:

• Strict schema: every Person MUST have name. Slower writes.
• Loose schema: anything goes. Faster writes. Queries need to handle missing properties.

Most graph DBs default to loose schema with optional constraints.

Edge type indexes:

• (:Person)-[:KNOWS]->() benefits from indexing edges by type.
• Per-type adjacency lists: KNOWS edges of node X → small list.
• Slows insertion slightly; speeds traversals significantly.

Statistics:

• Per-label cardinality (# of Persons).
• Per-(label, property) histogram.
• Used by query optimizer to pick join order.

Updates:

• Adding a label = update bitmap + add to per-label list.
• Adding an indexed property = insert into index + update node.
• Atomicity via WAL.

Index maintenance: rebuild periodically? Online updates? Most production systems do online updates, accept some slowdown during build.