• 검색 결과가 없습니다.

Chapter 1

N/A
N/A
Protected

Academic year: 2021

Share "Chapter 1"

Copied!
14
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

File Structures Chapter 1

Introduction to the Design and

Specification of File Structures

(2)

Outline

• What are File Structures?

• Why Study File Structure Design

• Overview of File Structure Design

(3)

Definition

• File Structure

– a combination of representations for data in files and operations for accessing the data

– It allows applications to read, write and modify data.

– It might also support finding the data that

matches some search criteria or reading through the data in some particular order.

(4)

Why Study File Structure Design?

I. Memory versus Secondary Storage

• Computer Memory (RAM) is very fast, but limited.

• Secondary storage such as disks can save thousands of megabytes in a small physical location.

• However, access to secondary storage is very slow

– E.g., getting information from RAM takes about 100 nanoseconds (= 100 * 10-9 seconds), while getting

information from Disk takes 30 milliseconds (= 30 * 10-3 seconds)

(5)

Why Study File Structure Design?

II. How Can Secondary Storage Access Time be Improved?

By improving the File Structure.

The details of the representation of the data and the implementation of the operations determine the efficiency of the file structure

 Improving these details can improve

secondary storage access time

(6)

Overview of File Structure Design I. General Goals

• Get the information we need with one access to the disk.

• If that’s not possible, then get the

information with as few accesses as possible.

• Group information so that we can get

everything we need with only one trip to the

disk.

(7)

Overview of File Structure Design II. Fixed versus Dynamic Files

• When the files never change

– It is easy to come up with file structure designs that meet the general goals.

• When files grow or shrink when information is added and deleted

– It is much more difficult.

(8)

History of File Structures I. Early Work

• Early Work assumed that files were on tape.

• Access was sequential

– the cost of access grew in direct proportion to the size of the file.

(9)

History of File Structures II. The emergence of Disks and Indexes

• As files grew very large, sequential access was not a good solution.

• Disks allowed for direct access.

– Indexes made it possible to keep a list of keys and pointers in a small file that could be searched very quickly.

– With the key and pointer, the user had direct

(10)

History of File Structures

III. The emergence of Tree Structures

• Indexes also have a sequential flavor

• when they grow too much, they also become difficult to manage.

• The idea of using tree structures to manage the index emerged in the early 60’s.

• However, trees can grow very unevenly as records are added and deleted

• resulting in long searches requires many disk accesses to find a record.

(11)

History of File Structures IV. Balanced Trees

• In 1963, researchers came up with the idea of AVL trees for data in memory.

• However, AVL trees did not apply to files

• because they work well when tree nodes are composed of single records rather than dozens or hundreds of them.

• In the 1970’s came the idea of B-Trees which require an O(logk N) access time

• where N is the number of entries in the file and k is the number of entries indexed in a single block of the B-Tree structure

•  B-Trees can guarantee that we can find an entry among

(12)

History of File Structures V. Hash Tables

• Retrieving entries in 3 or 4 accesses is good

• but it does not reach the goal of accessing data with a single request.

• Hashing was a good way to reach this goal with files that do not change size greatly over time.

• Recently, Extendible Dynamic Hashing

guarantees one or at most two disk accesses no

matter how big a file becomes.

(13)

C++ Class: Person

class Person { public:

// data members

char LastName[11], FirstName[11], Address[16];

char City[16], State[3], ZipCode[10];

// method

Person(); // constructor

(14)

C++ Class: Person – cont’d

Person::Person () {

// set each field to an empty string

LastName[0] = 0; FirstName[0] = 0; Address[0] = 0;

City[0] = 0; State[0] = 0; ZipCode[0] = 0;

};

int main() {

Person p; // automatic creation

Person *p_ptr = new Person(); // dynamic creation

참조

관련 문서

Now that you have the right bike for you, it is important to learn the right riding position.. A poor riding position can lead to injuries

44 글의 첫 번째 문장인 The most important thing in the Boat Race is harmony and teamwork.을 통해 Boat Race에서 가장 중요한 것은 조 화와 팀워크임을

 The Dutch physicist Pieter Zeeman showed the spectral lines emitted by atoms in a magnetic field split into multiple energy levels...  With no magnetic field to align them,

Modern Physics for Scientists and Engineers International Edition,

If both these adjustments are considered, the resulting approach is called a bootstrap-BC a -method (bias- corrected-accelerated). A description of this approach

After considering these objective structural imperatives of the existing system, I use the concrete standpoint of autonomous movements to evaluate current theories of

③ A student who attended Korean course at KNU Korean Language Program and holds TOPIK Level 3 or a student who completed Korean course Level 4 at the KNU Korean Language

· 50% exemption from tuition fee Ⅱ for the student with a TOPIK score of level 3 or higher or completion of level 4 or higher class of the Korean language program at the