Until now we have measured in units of number of operations. This measure is appropriate if the whole data structure can be stored in cache. But for large data structures not all of the data can be stored in cache. In this case portions of the data structure must be stored in external memory, which is usually a disk. Accessing data on a disk is much slower then accessing data in cache. For large data structures the appropriate measuring unit for time is number of disk transfers.
Memory in the computer is organized in a hierarchy. The RAM is generally called the main/primary memory. The secondary memory is generally the external memory device, the disk. Our goal is to minimize the number of disk transfers, or secondary memory accesses, needed to perform a query or update. The main memory is also organized in a hierarchy, cache and RAM. Accesses to the cache are faster then RAM. The computer microprocessor has registers, numbered 8 to 48. Registers can be consider the fastest memory. The lesson is that even for modestly sized data structures algorithms can be more efficient if we consider memory hierarchy and accesses. The principles discussed in this lecture can be applied to all levels of memory hierarchy. But disk access can be so slow as to make a program unusable.
Analyzing the performance of an ADT by counting the number of disk transfers is called I/O complexity.
Data stored in disk are grouped into contiguous sections called blocks. Lets say that a block can hold B nodes of the log file's link list. For the log file we could make a Block class that holds b nodes. For inserting, the node is placed in the last Block if the Block is not filled, otherwise a new Block is created.
Assuming that the log file is an unsorted link list then searching takes O(n) I/O complexity. With the Block class searching becomes O(n/B) time. Much better.
Using a sorted sequence then the we could perform the search in O(lg n) using a binary search. But then then insertion takes O(n/B) time.
We conclude that sequence based algorithm are not efficient implementations that require secondary memory.
Methods are performed in O(lg n). The secondary memory access can be as much as O(lg n/B) = O(lg n - lg B) = O(lg n). We would like to do better.
In order to limit secondary memory access we are willing to perform more primary memory accesses, perhaps as many as O(B) where B is the primary memory size. But O(B) high speed, primary memory accesses is better then a single disk transfer.
For (a, b) multi-way search tree each node has between a and b children and stores up to a-1 to b-1 items in the node. The (a, b) tree is a generalization of the (2, 4) tree.
With the additional constraint: a ≤ (b + 1)/2
Each internal node has at least a children (unless it is the root of a small tree) and no more then b children.
All external nodes have the same depth
The height of an (a, b) tree storing n items is Omega(lg n / lg b) and O(lg n/lg a).
Overflow occurs when an item is inserted into a b-node v, which becomes an illegal (b+1)-node. We split the node v by moving the median item of v into the parent of v and replacing v with two ~ ( b + 1)/2 nodes, v' and v''. (The reason for the a ≤ (b + 1)/2 property, so that splitting does not invalidate the size property)
An underflow can occur during removal. To remedy an underflow we can either perform a transfer with the nearest sibling that is not an a-node, or a fusion with the nearest sibling that is an a-node. (Again a reason for the a ≤ (b + 1)/2 property).
|
Method |
Time |
|
find |
O(f(b) lg n/lg a) |
|
insert |
O(g(b) lg n/lg a) |
|
remove |
O(g(b) lg n/lg a) |
where f(b) is time required to search the secondary data structure and g(b) is the time for split or fusion.
We choose a and b such that memory is used efficiently.
B-Tree is a version of the (a, b) trees where d = b = 2a, a B-tree of order d.
d should be chosen such that the d items and d-1 references is equal to one block size, B.
A B-tree with n items has I/O complexity O(logBn) for search or update and uses O(n/B) blocks, where B is the size of a block.