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.