DOC PREVIEW
UT Dallas CS 6360 - CS-6360 Chapter 17-FileStructuresHashing EMSE

This preview shows page 1-2-3-4-5-6-41-42-43-44-45-46-83-84-85-86-87-88 out of 88 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 88 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

!" #Dr. Chris Irwin Davis Email: [email protected] Phone: (972) 883-3574 Office: ECSS 4.705Chapter 17: File Structures and HashingCS-6360 Database Design!" #Outline• Placing File Records on Disk• Operations on Files• Files of Unordered Records (Heap Files)• File of Ordered Records (Sorted Files)• Hashing techniques• Other Primary File Organizations• Parallelizing Disk Access Using RAID• New Storage Systems!2!" #Placing File Records On Disk• Data is usually stored in the form of records. • Each record consists of a collection of related data values or items, where each value is formed of one or more bytes and corresponds to a particular field of the record.• Records usually describe entities and their attributes.3!" #Placing File Records On Disk• For example, an EMPLOYEE record represents an employee entity, and each field value in the record specifies some attribute of that employee, such as Name, Birth_date, Salary, or Supervisor.• A collection of field names and their corresponding data types constitutes a record type or record format definition. • A data type, associated with each field, specifies the types of values a field can take.4!" #Data Types and Size• The data type of a field is usually one of the standard data types used in programming (e.g. numeric, string, Boolean, sometimes Date and/or Time).• The number of bytes required for each data type is fixed for a given computer system.°Software platform dependent°Hardware platform dependent5!" #Records• For example, an EMPLOYEE record type may be defined—using the C programming language notation—as the following structure:6!" #BLOBs• The need may arise for storing data items that consist of large unstructured objects, which represent images, digitized video or audio streams, or free text. • These are referred to as BLOBs (binary large objects). • A BLOB data item is typically stored separately from its record in a pool of disk blocks, and a pointer to the BLOB is included in the record7Files, Fixed-Length Records, !and Variable-Length Records!" #Files, Fixed-Length Records, and Variable-Length Records• A file is a sequence of records. • In many cases, all records in a file are of the same record type. • If every record in the file has exactly the same size (in bytes), the file is said to be made up of fixed-length records. • If different records in the file have different sizes, the file is said to be made up of variable-length records. 9!" #Variable-Length Records• A file may have variable-length records for several reasons:°The file records are of the same record type, but one or more of the fields are of varying size (variable-length fields). For example, the Name field of EMPLOYEE can be a variable-length field.°The file records are of the same record type, but one or more of the fields may have multiple values for individual records; such a field is called a repeating field and a group of values for the field is often called a repeating group.10!" #Variable-Length Records• The file records are of the same record type, but one or more of the fields are optional; that is, they may have values for some but not all of the file records (optional fields).• The file contains records of different record types and hence of varying size (mixed file). This would occur if related records of different types were clustered (placed together) on disk blocks; for example, the GRADE_REPORT records of a particular student may be placed following that STUDENT’s record.11!" #Record Storage Formats12!" #Record Storage Formats13!" #Record Storage Formats1417.5 Operations on Files!" #Operations on Files• OPEN: Readies the file for access, and associates a pointer that will refer to a current file record at each point in time.• FIND: Searches for the first file record that satisfies a certain condition, and makes it the current file record.• FINDNEXT: Searches for the next file record (from the current record) that satisfies a certain condition, and makes it the current file record.• READ: Reads the current file record into a program variable.• INSERT: Inserts a new record into the file & makes it the current file record. 16!" #Operations on Files• DELETE: Removes the current file record from the file, usually by marking the record to indicate that it is no longer valid.• MODIFY: Changes the values of some fields of the current file record.• CLOSE: Terminates access to the file.• REORGANIZE: Reorganizes the file records.°For example, the records marked deleted are physically removed from the file or a new organization of the file records is created.• FIND_ORDERED: Retrieves all the records in the file in some specified order.• READ_ORDERED: Read the file blocks in order of a specific field of the file. 1717.6 Files of Unsorted Records (Heap Files) 17.7 Files of Sorted Records (Sorted Files)!" #Unordered Records (Heap Files)• Also called a heap or a pile file.• New records are inserted at the end of the file.• A linear search through the file records is necessary to search for a record.°This requires reading and searching half the file blocks on the average, and is hence quite expensive.• Record insertion is quite efficient °Just throw it on the heap• Reading the records in order of a particular field requires sorting the file records. 19!" #Ordered Records (Sorted Files)• Also called a sequential file.• File records are kept sorted by the values of an ordering field.• Insertion is expensive: records must be inserted in the correct order.• It is common to keep a separate unordered overflow (or transaction) file for new records to improve insertion efficiency; °this is periodically merged with the main ordered file.20!" #Ordered Records (Sorted Files)• A binary search can be used to search for a record on its ordering field value.• This requires reading and searching log2 of the file blocks on the average (i.e. binary search), an improvement over linear search.• Reading the records in order of the ordering field is quite efficient.21Memory Blocks of a Sorted File!" #23!" #Other Strategies to Organize Data• What if data were evenly distributed among memory “buckets”?• Which field to sort / order by?• How to insure even distribution?24Hashing!" #Hashing• Another type of primary file organization is based on hashing, which provides very fast access to records under certain search conditions. • This organization is


View Full Document

UT Dallas CS 6360 - CS-6360 Chapter 17-FileStructuresHashing EMSE

Documents in this Course
Ch22(1)

Ch22(1)

44 pages

Ch21

Ch21

38 pages

Ch19

Ch19

46 pages

Ch18

Ch18

25 pages

Ch17

Ch17

21 pages

Ch15

Ch15

42 pages

Ch09

Ch09

42 pages

Ch05

Ch05

34 pages

Ch22

Ch22

45 pages

Ch21

Ch21

38 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch16

Ch16

17 pages

Ch15

Ch15

42 pages

Ch09

Ch09

42 pages

Ch08

Ch08

39 pages

Ch07

Ch07

34 pages

Ch06

Ch06

43 pages

Ch05

Ch05

34 pages

Ch04

Ch04

39 pages

Ch03(2)

Ch03(2)

36 pages

Ch02

Ch02

33 pages

Ch08

Ch08

28 pages

Ch07

Ch07

31 pages

Ch06

Ch06

43 pages

Ch05

Ch05

39 pages

Ch04(1)

Ch04(1)

39 pages

Ch03(1)

Ch03(1)

38 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch24

Ch24

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch03(1)

Ch03(1)

38 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch24

Ch24

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

48 pages

Ch18

Ch18

24 pages

Ch17

Ch17

22 pages

Ch08

Ch08

28 pages

Ch07

Ch07

31 pages

Ch06

Ch06

43 pages

Ch05

Ch05

39 pages

Ch04(1)

Ch04(1)

39 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

lab-manual

lab-manual

215 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch17

Ch17

25 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04

Ch04

43 pages

Ch03

Ch03

41 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Ch04(1)

Ch04(1)

43 pages

Ch07

Ch07

40 pages

Ch03

Ch03

42 pages

Ch01

Ch01

36 pages

Ch02

Ch02

38 pages

Ch05

Ch05

41 pages

Ch06

Ch06

47 pages

Ch08

Ch08

39 pages

Ch17

Ch17

25 pages

Ch18

Ch18

24 pages

Ch09

Ch09

42 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch21

Ch21

54 pages

Ch19

Ch19

51 pages

Ch18

Ch18

24 pages

Ch17

Ch17

25 pages

Ch09

Ch09

42 pages

Ch08

Ch08

39 pages

Ch07

Ch07

40 pages

Ch06

Ch06

47 pages

Ch05

Ch05

41 pages

Ch04(1)

Ch04(1)

43 pages

Ch03

Ch03

42 pages

Ch02

Ch02

38 pages

Ch01

Ch01

36 pages

Load more
Download CS-6360 Chapter 17-FileStructuresHashing EMSE
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS-6360 Chapter 17-FileStructuresHashing EMSE and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS-6360 Chapter 17-FileStructuresHashing EMSE 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?