حل الاسؤال الاول من هذا السلايد
Example: Given the following data file EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL, ... )
Suppose that:
record size R=150 bytes block size B=512 bytes r=3 0000 records
Then, we get:
blocking factor Bfr= B div R= 512 div 150= 3 records/block
number of file blocks b= (r/Bfr)= (3 0000/3)= 10000 blocks
For an index on the SSN field, assume the field size VSSN=9 bytes, assume the record pointer size PR=7 bytes. Then:
index entry size RI=(VSSN+ PR)=(9+7)=16 bytes
index blocking factor BfrI= B div RI= 512 div 16= 32 entries/block
number of index blocks b= (r/ BfrI)= (3 0000/32)= 938 blocks
binary search needs log2bI= log2938= 10 block accesses
This is compared to an average linear search cost of:
(b/2)= 3 0000/2= 15000 block accesses
If the file records are ordered, the binary search cost would be:
log2b= log23 0000= 15 block accesses
طبق المعادله ويطلع الجواب كامل
b
الكتاب ص 633
Aprimary indexis an ordered file whose records are of fixed length with two fields,
and it acts like an access structure to efficiently search for and access the data
records in a data file. The first field is of the same data type as the ordering key
field—called the primary key—of the data file, and the second field is a pointer to a
disk block (a block address). There is one index entry (orindex record) in the
index file for each blockin the data file. Each index entry has the value of the primary key field for the first record in a block and a pointer to that block as its two
field values. We will refer to the two field values of index entry ias <K(i),P(i)>.
To create a primary index on the ordered file shown in Figure 17.7, we use the Name
field as primary key, because that is the ordering key field of the file (assuming that
each value ofNameis unique). Each entry in the index has a Namevalue and a
pointer. The first three index entries are as follows:
<K(1) = (Aaron, Ed),P(1) = address of block 1>
<K(2) = (Adams, John),P(2) = address of block 2>
<K(3) = (Alexander, Ed),P(3) = address of block 3>
Figure 18.1 illustrates this primary index. The total number of entries in the index is
the same as the number of disk blocksin the ordered data file. The first record in each
block of the data file is called the anchor recordof the block, or simply the block
anchor.
2
Indexes can also be characterized as dense or sparse. A dense indexhas an index
entry for every search key value(and hence every record) in the data file. A sparse
(ornondense)index, on the other hand, has index entries for only some of the
search values. A sparse index has fewer entries than the number of records in the
file. Thus, a primary index is a nondense (sparse) index, since it includes an entry
for each disk block of the data file and the keys of its anchor record rather than for
every search value (or every record).