Row Store and Column Store

	Data Structures	Source Location
	WT_BTREE	src/include/btree.h

Caution: the Architecture Guide is not updated in lockstep with the code base and is not necessarily correct or complete for any specific release.

Definition

WiredTiger supports both row-stores and column-stores and each access method is represented internally by a B-Tree. Keys and values in row-stores can be of variable length. Furthermore, keys are explicitly stored. Column-stores use a 64-bit unsigned integer record id as keys and they are implied given the row's position in the B-Tree.

Please refer to Data File Format to learn more about the on-disk format for row-stores and column-stores.

Row-stores

Row-stores are probably seen as the traditional access method and they serve a general purpose. In WiredTiger, row-store keys are explicitly stored and they can be duplicated within the same single file which directly impacts the on-disk storage size. However, keys are only duplicated if they are the first key on the page, which gets them copied/promoted to an internal page. They are not necessarily duplicated, too, they can be prefix/suffix compressed to discard unnecessary bytes on the internal pages.

Variable length column-stores

Keys in column-stores are not stored but derived from the row's position in the B-Tree which saves disk space. In fact, there is a starting key on each page which is used to figure out the rest of the keys present on that same page. Column-stores values also present an advantage to further save more disk space as they can be written in more compact forms through encoding techniques. In WiredTiger, the run-length encoding is used to replace any sequence of the same value with a count and value indicator. However, this makes the access to a specific record more complicated, it makes it impossible to jump to a record in a leaf page.

Internal usage

Internally, row-stores and column-stores use a common WT_BTREE structure. The fundamental difference is that the WT_BTREE->type field is set to BTREE_ROW for row-stores and BTREE_COL for column-stores. Internal functions that navigate, access and manipulate B-Trees have code sprinkled throughout that is conditional on WT_BTREE->type.

	Row Store	Column Store - Variable Length
Characteristics
Internal representation	B-Tree (WT_BTREE)	B-Tree (WT_BTREE)
B-Tree type	Generalized (BTREE_ROW)	Specialized (BTREE_COL_VAR)
Leaf pages	Key count equal to half the number of physical entries (unless all empty values flag is set where key count is equal to the number of physical entries)	Only the first key is stored
Record key	Anything (byte-string) prefix compressed or overflow objects	Record id (64 bit unsigned integer)
Record value	Variable byte string length	Variable byte string length
Features
Random cursor	Yes	No
Block compression	Yes	Yes
Dictionary compression	Yes	Yes
Fast truncate	Yes	No
Prefix and suffix compression	Yes	No
RLE compression	No	Yes