Vocabulary

B-tree

Data structure used to represent a very large set.

 

binary format

Format of files stored as data rather than text.

 

buffered

Of an input or output stream, waiting until it has a large chunk of data before actually sending it.

 

compressed

Of a file, stored in a format that uses fewer bits. Compressing or uncompressing a file takes time but saves space on disk or transmission time over a network.

 

external sorting

Sorting performed using files, for use when the data set is too large to fit in memory.

 

fixed-length encoding

Any encoding, such as ASCII, in which each character is represented by the same number of bits.

 

flush

Force a buffered stream to send data.

 

full

Of a B-tree node, having the largest allowable number of elements (one more than twice as many as in a minimal node).

 

Huffman encoding

Encoding in which more frequent characters are represented by shorter bit sequences.

 

LempelZiv encoding

Encoding in which each code may represent a long string of characters.

 

merge

Join two minimal B-tree nodes, plus an element pulled down from the parent, into a full node.

 

minimal

Of a B-tree node, having the smallest allowable number of elements.

 

run

Sorted sequence of elements used in external sorting.

 

serialization

Process of storing a directed graph of objects in memory in a linear file on disk.

 

size

Of a B-tree node, one more than the number of elements in the node.

 

split

Divide a full B-tree node into two minimal nodes and one extra element, which is moved up into the parent.