Sparse Arrays

Alright /proglodites/, let's hear how all of you implement a sparse arrays that stores two-dimensional data.

Have some kind of tree with the following data types

root node
;;majority value
;;index
;;value

data type:
;;index
;;value

When storing data to the array it is first checked against the majority value for that set, if the value is not equal to the majority value it is stored in the tree with its index number. otherwise it is discarded. Retrival works like a binary tree.

At least that's how I would do it. Keep in mind I have zero idea about how this *should* be done.