Databases Reference
In-Depth Information
p
key values. The total number of pointers over all nodes at that level (
h
) must be greater
than or equal to the number of rows in the table (
n
). Therefore, our estimate becomes
p
h
>
n
h
log
p
> log
n
h
> log
n
/log
p
2.2
In this case, for
n
= 500,000 rows and
p
= 50 pointers per node, the height (
h
) of the
B+tree becomes
h
> 3.35 or
h
= 4.
A query to a particular row in a B+tree is simply the time required to access all
h
levels of the tree index plus the access to the data row (within a block or page). All
accesses to different levels of index and data are assumed to be random.
Read a single row in a table (using a B+tree)
=
h
+ 1 block accesses.
2.3
Updates of rows in a B+tree can be accomplished with a simple query and rewrite
unless the update involves an insertion that overflows a data or index node or a deletion
that empties a data or index node. A rewrite of a row just read tends to be a random
block access in a shared disk environment, which we assume here. For the simple case of
updating data values in a particular row, assume that each index node is implemented as
a block.
Update cost for a single row (B+tree)
= search cost + rewrite data block
= (
h
+ 1) + 1
=
h
+ 2 block accesses,
2.4
where a block access is assumed to be an access to an individual block (or page) in a
shared disk environment.
If the operation desired is an insertion and the insertion causes overflow of a data or
leaf index node, additional accesses are needed to split the saturated node into two
nodes that are half filled (using the basic splitting algorithm) plus the need to rewrite
the next higher index node with a new pointer to the new index node (see Figure 2.2).
The need for a split is recognized after the initial search for the row has been done. A
split of an leaf index node requires a rewrite of the saturated leaf index node, half filled
with data, plus a write of a new leaf index node also half filled, plus a rewrite of the non-
leaf index node with a new pointer value to the new leaf index node.
