Please enable JavaScript.
Coggle requires JavaScript to display documents.
indexing structures for fiels and physical DB design(cha 17) - Coggle…
indexing structures for fiels and physical DB design(cha 17)
access structures called indexes,
what
additional files on disk that provide secondary access paths, which
provide alternative ways to access the records without affecting the physical placement of records in the primary data file on disk.
why
used to speed up the retrieval of records in response to certain search conditions.
Single-Level Ordered Indexes
indexing
field (or indexing attribute).
For a file with a given record structure consisting of several fields (or attributes), an index access structure is usually defined on a single field of a file
stores each value of the index field along with a list of pointers to all disk blocks that contain records with that field value.
types of ordered indexes
primary index
is specified on the
ordering key field of an ordered file of records
A primary index is an ordered file whose records are of fixed length with two fields； each <K(i), P(i)>
value of the primary key field for the first record in a block
a pointer to one block
physical address of a block (or page) in the file
record address made up of a block address and a record id (or
offset) within the block.
logical address of the block or of the record within the file and is
a relative number that would be mapped to a physical address
numerous records in the file can have the same value for the ordering field— a
clustering index
The data file is called
a clustered file
a file can have at most one physical ordering field
？？
a secondary index, can be specified on any
nonordering field of a file
Multilevel Indexes
multilevel index is to reduce the part of the index that we continue to search by bfri, the blocking factor for the index, which is larger than 2
bfri is called the fan-out of the multilevel
index, and we will refer to it by the symbol fo.
We can repeat the preceding process until all the entries of some index level t fit in a single block.
1 ≤ (r1/((fo)t)) to calculate t.
t= 0: first level has r1
Dynamic Multilevel Indexes Using
B-Trees and B+-Trees
B-Trees. The B-tree has additional constraints that ensure that the tree is always balanced and that the space wasted by deletion, if any, never becomes excessive
Each B-tree node can have at most p tree pointers, p − 1 data pointers, and p − 1 search key field values
In a B+-tree, data pointers are stored
only at the leaf nodes of the tree
Indexes on Multiple Keys