The three types of NoSQL databases I've read about is key-value, wide-column, and document-oriented.
Key-value is pretty straight forward - a key with a plain value.
I've seen document-oriented databases described as like key-value, but the value can be a structure, like a JSON object. Each "document" can have all, some, or none of the same keys as another.
Wide-column seems to be very much like document oriented in that you don't specify a structure.
So what is the difference between these two, and why would you use one over the other?
I've specifically looked at MongoDB and Cassandra. I basically need a dynamic structure that can change, but not affect other values. At the same time I need to be able to search/filter specific keys and run reports. With CAP, AP is the most important to me. The data can "eventually" be synced across nodes, just as long as there is no conflict or loss of data. Each user would get their own "table".
In Cassandra, each row (addressed by a key) contains one or more "columns". Columns are themselves key-value pairs. The column names need not be predefined, i.e. the structure isn't fixed. Columns in a row are stored in sorted order according to their keys (names).
In some cases, you may have very large numbers of columns in a row (e.g. to act as an index to enable particular kinds of query). Cassandra can handle such large structures efficiently, and you can retrieve specific ranges of columns.
There is a further level of structure (not so commonly used) called super-columns, where a column contains nested (sub)columns.
You can think of the overall structure as a nested hashtable/dictionary, with 2 or 3 levels of key.
Normal column family:
row
col col col ...
val val val ...
Super column family:
row
supercol supercol ...
(sub)col (sub)col ... (sub)col (sub)col ...
val val ... val val ...
There are also higher-level structures - column families and keyspaces - which can be used to divide up or group together your data.
See also this Question: Cassandra: What is a subcolumn
Or the data modelling links from http://wiki.apache.org/cassandra/ArticlesAndPresentations
Re: comparison with document-oriented databases - the latter usually insert whole documents (typically JSON), whereas in Cassandra you can address individual columns or supercolumns, and update these individually, i.e. they work at a different level of granularity. Each column has its own separate timestamp/version (used to reconcile updates across the distributed cluster).
The Cassandra column values are just bytes, but can be typed as ASCII, UTF8 text, numbers, dates etc.
Of course, you could use Cassandra as a primitive document store by inserting columns containing JSON - but you wouldn't get all the features of a real document-oriented store.