need to support efficient sequential read as well. b-tree

Hash table

Assuming sparse means many values are zero: have 2 arrays: one to store non-zero indexes, the other to store the values at the non-zero index. If queried number is not in the index set, return 0.