On Fri, Dec 24, 2010 at 6:42 PM, Zhu Han <schumi....@gmail.com> wrote:
> When the row is stored on disk as SSTable, the complexity of getting a row > is constant, as it always know where to get the row by in-memory indices. > BTW: not the whole indices are kept in memory, just part of them are. This is controlled by "IndexInterval". That is, 1/IndexInterval of whole indices are kept in memory. The default value is 128. > > When the row is stored in memory as memtable, it is stored as skip > list[1]. The complexity is O(logN). N is the total number of rows in the > skip list. > > To get a column inside a row, the complexity is similar. When there are > many columns in a single row, cassandra will build indices for these columns > when write the row to SStable. This controlled by "ColumnIndexSizeInKB". > > If I made any mistake, please correct me. Thank you! > > [1] http://en.wikipedia.org/wiki/Skip_list > > best regards, > hanzhu > > > > On Fri, Dec 24, 2010 at 12:20 PM, Kevin Irwig <kevinir...@yahoo.com>wrote: > >> Hi, >> >> I've seen a similar question has been asked in this forum in Sept, but not >> answered. >> >> What is the complexity of get(row) and get(row, column-name) operations, >> and >> insert(row, column)? What about accessing or inserting a column within a >> SuperColumn by name? >> >> In Arin Sarkissian's "WTF is a Supercolumn" he stresses that columns are >> stored >> sorted by name. Are they simply stored in a sorted list, requiring a >> search when >> inserting and accessing (I forget the worst case complexity of >> searching/inserting into/deleting from a sorted list), or in some data >> structure >> with faster access? Even if you don't know the big-O complexity, a >> description >> of the implementation data structure(s), and discussion of what is fast >> and what >> is not, would help. >> >> Thanks for your help, >> Kevin. >> >> >> >> >> >
