Define file organisation .

File organisation is the way records are arranged within a file .

What does a file store, and how?

It stores data permanently on secondary storage as a collection of records , where each record represents one item such as a customer, transaction or product.

Why does the choice of file organisation matter?

It affects how quickly records can be searched, added, updated and deleted , so it is chosen to suit the task.

True or False? File organisation and file access mean the same thing.

False. Organisation is how records are arranged in the file. Access is how records are read from it.

Name the three file organisation methods.

Serial , sequential and random .

Define serial file organisation .

Records are stored one after the other in the order they arrive , in chronological order with no sorting.

In a serial file, records are stored in order.

In a serial file, records are stored in chronological order.

Where are new records added in a serial file?

They are appended to the end of the file .

Give one drawback of serial file organisation.

It is slow to search , because there is no order to exploit .

What is serial organisation best for?

Unsorted or temporary transaction files and data logging files , for example logging sensor readings as they arrive.

Define sequential file organisation .

Records are stored in sorted order, based on a key field .

How is a sequential file updated?

A new version of the file has to be created , because records cannot easily be inserted in place.

True or False? A sequential file can be updated in place without rewriting it.

False. A new version of the file must be created. It is a random file that can be updated directly.

Why is a sequential file more efficient to search than a serial file?

A search can stop once the key is passed .

What is sequential organisation best for?

Files that are read often but rarely updated , such as payroll files or exam results ordered by candidate number.

Define random file organisation .

Records are stored in no particular order , with a hashing algorithm applied to the key to work out the address.

In a random file there is a relationship between the record's key and its .

In a random file there is a relationship between the record's key and its location .

How are random files updated?

Directly , without rewriting the file.

What is random organisation best for?

Fast, real-time access to individual records , such as bank account lookup or live stock updates.

Define file access method .

A file access method is how records are read from or located in a file, once the file has been organised.

Which access methods work on a serial file?

Sequential access only . Direct access is not possible on a serial file.

Which access methods work on a sequential file?

Both sequential access and direct access , with direct access using an index .

Which access methods work on a random file?

Direct access only , using hashing . Sequential access is not possible on a random file.

True or False? Direct access is possible on a serial file.

False. A serial file supports sequential access only .

Define sequential access .

Sequential access reads records one after the other , starting at the physical start of the file , and continues until the record is found or the end of the file is reached.

Sequential access starts at the start of the file.

Sequential access starts at the physical start of the file.

How does sequential access work on a serial file?

Records are in chronological order , so every record is checked until the target is found or all records have been checked.

How does sequential access work on a sequential file?

Records are in order of a key field or index , and it is the key field that is compared .

Why can sequential access stop early on a sequential file?

As soon as the current record's key is greater than the target key , the target cannot be present .

True or False? Sequential access and sequential organisation are the same thing.

False. They are different. Serial files also use sequential access .

Define direct access .

Direct access locates a specific record without reading the records before it , using the key field of the record.

How does direct access work on a random file?

A hashing algorithm is applied to the record's key field to calculate the address of the location where the record should be.

On a random file, if the record is not at the hashed address then a has occurred.

On a random file, if the record is not at the hashed address then a collision has occurred.

How does direct access work on a sequential file?

An index of all key fields is kept. The index is searched for the address of the record, which is then read directly.

What is the key difference between direct access on a random file and on a sequential file?

A random file uses a hashing algorithm . A sequential file uses an index .

Give an example of direct access in use.

Accessing a bank account record by account number .

Define hashing algorithm .

A hashing algorithm is a mathematical formula applied to the key field of a record , whose result gives the address where that record should be stored or found.

True or False? A hashing algorithm scrambles the data in a record.

False. A hashing algorithm is a mathematical formula applied to the key field , and its result is an address . It does not scramble the record's data.

Hashing gives access to a record without searching through the file one record at a time.

Hashing gives fast access to a record without searching through the file one record at a time.

How is a record written using hashing?

Calculate the address from the key , then store the record at that address.

How is a record read using hashing?

Calculate the address from the same key , then read the record from that address.

Define modulo division hashing.

The address is calculated as Key MOD TableSize , which is the most common hashing method.

In hashing, MOD gives the after division.

In hashing, MOD gives the remainder after division.

Why does modulo division always give a valid address?

The remainder is always in the range 0 to TableSize minus 1 .

The key is split into equal parts , the parts are added together , and usually MOD TableSize is applied to the total.

A random file has 100 locations, addressed 0 to 99. Where is the record with key 45217 stored under modulo division?

45217 MOD 100 = 17 , so the record is stored at address 17 .

A record with key 88317 is added to the same 100-location file. What happens?

88317 MOD 100 = 17 , which is the same address as key 45217, so a collision occurs.

Define collision in hashing.

A collision is when two keys hash to the same address .

True or False? When two keys hash to the same address, the second record is discarded.

False. A collision resolution method is used, such as linear probing , an overflow area , or chaining .

A LevelComputer ScienceCambridge (CIE)Flashcards13. Data RepresentationFile Organisation & Access

File Organisation & Access (Cambridge (CIE) A Level Computer Science): Flashcards

Exam code: 9618

1/57

0Still learning

Know0

FrontFile Organisation
Define file organisation.

Was this flashcard helpful?

Cards in this collection (57)

Define file organisation.
File organisation is the way records are arranged within a file.
What does a file store, and how?
It stores data permanently on secondary storage as a collection of records, where each record represents one item such as a customer, transaction or product.
Why does the choice of file organisation matter?
It affects how quickly records can be searched, added, updated and deleted, so it is chosen to suit the task.
True or False?
File organisation and file access mean the same thing.
False.
Organisation is how records are arranged in the file. Access is how records are read from it.
Name the three file organisation methods.
Serial, sequential and random.
Define serial file organisation.
Records are stored one after the other in the order they arrive, in chronological order with no sorting.
In a serial file, records are stored in order.
In a serial file, records are stored in chronological order.
Where are new records added in a serial file?
They are appended to the end of the file.
Give one drawback of serial file organisation.
It is slow to search, because there is no order to exploit.
What is serial organisation best for?
Unsorted or temporary transaction files and data logging files, for example logging sensor readings as they arrive.
Define sequential file organisation.
Records are stored in sorted order, based on a key field.
How is a sequential file updated?
A new version of the file has to be created, because records cannot easily be inserted in place.
True or False?
A sequential file can be updated in place without rewriting it.
False.
A new version of the file must be created. It is a random file that can be updated directly.
Why is a sequential file more efficient to search than a serial file?
A search can stop once the key is passed.
What is sequential organisation best for?
Files that are read often but rarely updated, such as payroll files or exam results ordered by candidate number.
Define random file organisation.
Records are stored in no particular order, with a hashing algorithm applied to the key to work out the address.
In a random file there is a relationship between the record's key and its .
In a random file there is a relationship between the record's key and its location.
How are random files updated?
Directly, without rewriting the file.
What is random organisation best for?
Fast, real-time access to individual records, such as bank account lookup or live stock updates.
Define file access method.
A file access method is how records are read from or located in a file, once the file has been organised.
What determines which access methods are available?
The file organisation used.
Which access methods work on a serial file?
Sequential access only. Direct access is not possible on a serial file.
Which access methods work on a sequential file?
Both sequential access and direct access, with direct access using an index.
Which access methods work on a random file?
Direct access only, using hashing. Sequential access is not possible on a random file.
True or False?
Direct access is possible on a serial file.
False.
A serial file supports sequential access only.
Define sequential access.
Sequential access reads records one after the other, starting at the physical start of the file, and continues until the record is found or the end of the file is reached.
Sequential access starts at the start of the file.
Sequential access starts at the physical start of the file.
How does sequential access work on a serial file?
Records are in chronological order, so every record is checked until the target is found or all records have been checked.
How does sequential access work on a sequential file?
Records are in order of a key field or index, and it is the key field that is compared.
Why can sequential access stop early on a sequential file?
As soon as the current record's key is greater than the target key, the target cannot be present.
True or False?
Sequential access and sequential organisation are the same thing.
False.
They are different. Serial files also use sequential access.
Define direct access.
Direct access locates a specific record without reading the records before it, using the key field of the record.
How does direct access work on a random file?
A hashing algorithm is applied to the record's key field to calculate the address of the location where the record should be.
On a random file, if the record is not at the hashed address then a has occurred.
On a random file, if the record is not at the hashed address then a collision has occurred.
How does direct access work on a sequential file?
An index of all key fields is kept. The index is searched for the address of the record, which is then read directly.
What is the key difference between direct access on a random file and on a sequential file?
A random file uses a hashing algorithm. A sequential file uses an index.
Give an example of direct access in use.
Accessing a bank account record by account number.
Define hashing algorithm.
A hashing algorithm is a mathematical formula applied to the key field of a record, whose result gives the address where that record should be stored or found.
True or False?
A hashing algorithm scrambles the data in a record.
False.
A hashing algorithm is a mathematical formula applied to the key field, and its result is an address. It does not scramble the record's data.
Hashing gives access to a record without searching through the file one record at a time.
Hashing gives fast access to a record without searching through the file one record at a time.
How is a record written using hashing?
Calculate the address from the key, then store the record at that address.
How is a record read using hashing?
Calculate the address from the same key, then read the record from that address.
Name the two types of hashing algorithm.
Modulo division and folding.
Define modulo division hashing.
The address is calculated as Key MOD TableSize, which is the most common hashing method.
In hashing, MOD gives the after division.
In hashing, MOD gives the remainder after division.
Why does modulo division always give a valid address?
The remainder is always in the range 0 to TableSize minus 1.
Define folding.
The key is split into equal parts, the parts are added together, and usually MOD TableSize is applied to the total.
A random file has 100 locations, addressed 0 to 99.
Where is the record with key 45217 stored under modulo division?
45217 MOD 100 = 17, so the record is stored at address 17.
A record with key 88317 is added to the same 100-location file.
What happens?
88317 MOD 100 = 17, which is the same address as key 45217, so a collision occurs.
Define collision in hashing.
A collision is when two keys hash to the same address.
True or False?
When two keys hash to the same address, the second record is discarded.
False.
A collision resolution method is used, such as linear probing, an overflow area, or chaining.
Name the three collision resolution methods.
Linear probing, an overflow area, and chaining.
Define linear probing.
Start at the hashed address and move through the following locations in a linear fashion, storing the record in the first free location.
Key 88317 collides at address 17.
Using linear probing, where is the record stored?
In the next free location, address 18.
How does an overflow area resolve a collision?
A separate overflow area is set up, and the record is stored in the next free space there.
Define chaining.
Each location holds a reference to a list, or chain, of records that hashed to it, and the new record is added to that chain.
Why is it not enough to name a collision resolution method in an exam?
You must also describe how it resolves the collision, for example 'linear probing, store in the next free location'.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:User-defined Data TypesNext:Floating-point Numbers, Representation & Manipulation