TASK
Implementation
Implement secondary indexes for non-key attributes:
- Primary index: primary_key -> data
- Secondary index: attribute_value -> list of primary_keys
- Query by attribute: secondary lookup, then primary lookups
- Keep secondary index updated on all writes/deletes
Secondary indexes enable efficient queries on any attribute, not just the primary key.
Sample Test Cases
Secondary index lookupTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"db_insert","msg_id":2,"id":1,"name":"Alice","status":"active"}}
{"src":"c2","dest":"n1","body":{"type":"db_insert","msg_id":3,"id":2,"name":"Bob","status":"active"}}
{"src":"c3","dest":"n1","body":{"type":"db_query","msg_id":4,"field":"status","value":"active"}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c1","body":{"type":"db_insert_ok","in_reply_to":2,"msg_id":1}}
{"src":"n1","dest":"c2","body":{"type":"db_insert_ok","in_reply_to":3,"msg_id":2}}
{"src":"n1","dest":"c3","body":{"type":"db_query_ok","in_reply_to":4,"msg_id":3,"results":[1,2]}}
Hints
Hint 1▾
Secondary index maps attribute to primary keys
Hint 2▾
Update secondary index on data changes
Hint 3▾
Handle one-to-many relationships
OVERVIEW
Theoretical Hub
Secondary Indexes
Primary indexes organize data by primary key. But what if you need to find users by email or orders by status? Secondary indexes provide alternative access paths for these non-key queries.
Implementation Approaches
1. Separate index file mapping attribute -> primary keys. 2. Covering index includes full record to avoid primary lookup. 3. Inverted index for text search.
Key Concepts
secondary indexnon-key lookupinverted index
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/env python3
import sys
import json
from collections import defaultdict
class IndexedTable:
def __init__(self, primary_key_field):
self.pk_field = primary_key_field
self.data = {} # primary_key -> record
self.secondary_indexes = {} # field -> (value -> set of pks)
def create_index(self, field):
# TODO: Create secondary index on field
pass
def insert(self, record):
# TODO: Insert record, update all indexes
pass
def delete(self, primary_key):
# TODO: Delete record, update all indexes
pass
def query_by_index(self, field, value):
# TODO: Use secondary index to find records
pass
def query_range(self, field, min_val, max_val):
# TODO: Range query using index
pass
if __name__ == "__main__":
table = IndexedTable("id")
table.create_index("status")