Introduction and Overview

• Row-oriented databases are most useful when we have to access data by row, storing entire rows toegher improves spatial locality.
• Column-oriented are a good fit for analytical workloads that compute aggregates.

Column Oriented

To reconstruct data tuples, which might be useful for joings, filtering and multirow aggregates, we need to preserve some metadata on the column level to identify which data points from other columns it is associated with. If you do this explicitly, each value will hold a key, which introduces duplication and increases the amount of stored data. Some column stores use implicit identifiers (virtual IDS) instead and use the position of the value (in other words its offset) to map it back to the related values.

Data Files and Indexes

Data files (sometimes called primary files) can be implemented as index-organized tables, heap-organized tables, or hash-organized tables.

An index on a primary (data) file is called the primary index. In most cases we can assume that the primary index is build over a primary key or a set of keys identified as primary. All other indexes are called secondary.

Secondary indexes can point directly to the primary (data) file or point to the Primary index instead. Pointing to the primary index will be faster for writes where the database needs to update the secondary indexes, but slower to read (since there will be one more disk seek).

B-tree basics

BST (binary search trees) can be balanced by performing a rotation step after nodes are added or removed. If the insert operation leaves a branch unbalanced (two consecutive nodes in the branch have only one chiild), we can rotate nodes around the middle one (check img on page 28)

BSTs have low fanout (fanout is the maximum allowed number of childer per node), so we have to perform balacing, relocate nodes and update pointers rather frequently.

Increased maintenance costs make BSTs impratical as on-disk data structures. Also, because elements are added in random order, there is no guarantee that a newly created node is written close to its parent, which means that node child pointers may span across several disk pages.

On-Disk Structures

The main limitation and design condition for building efficient on-disk structures is the fact that the smallest unit of disk operation is a block.