External StorageIntroduction – External StorageSlide 3Accessing External Data A Very Different Ballgame!Accessing External Data Very Slow AccessDisk Access – Four Key ComponentsSequential File Organization and AccessMore on Sequential FilesStill More on Sequential FilesB-Trees and IndexingB-TreesB-Trees – One Block per NodeB-Trees – SearchingB-Trees – Insertions - 1B-Trees – Insertions – 2B-Tree Insertion - 3 Example (Book)B-Tree Insertion -4 Example (Book)B-Trees – Insertion -5 Algorithm continuedB-Trees – Insertion -6 AlgorithmB-Tree EfficiencyB-Tree Efficiency – 2Variations of B-Trees ImplementationPowerPoint PresentationSlide 24Slide 25Slide 26Slide 27Slide 28Slide 29Indexed Sequential File OrganizationIndexed FileSlide 32Slide 33Index Sequential – more =- VSAM!!DirectoriesSlide 36Indexed File – Alternate KeysExternal StorageChapter 10Plus Considerable Instructor Notes from Other Sources.2Introduction – External Storage•One of the most important topics we will discuss.•We know about multi-way trees, such as 2-3-4 Trees, and these concepts generalize.•But when it comes to external storage, there are additional major considerations we must consider.3Introduction – External Storage•External Storage organization and access (not the same!!!) • External Storage – organization and retrieval are much different than those techniques applied to primary memory data structures and techniques!!!4Accessing External DataA Very Different Ballgame! The data structures so far: entirely in RAM (or primary memory)RAM – ‘random access memory’ is many orders of magnitude quicker than ‘random access disk access.’ MANY ORDERS OF MAGNITUDE!!.•RAM is very limiting indeed! Data is NOT persistent! –Amount of data limited by size of primary memory typically shared with many other concurrent users; –Data, of course, is volatile.•Advantage of Data Structures in RAM:: –For data structures, the Speed of RAM is very enticing. But for real IS / IT applications, many applications require external storage in the form of a database system or a file system. –Advantages of RAM for in-memory data structures are gone!•Disadvantage: –Persistence, number of data items (records) etc. –Amount of memory available to your process (program)•Significant IS applications in real world very often require lots of data to process. •External disk files - only practical way.  Disk processing is really the mainstay of information processing whether the files are legacy type, database files, etc5Accessing External Data Very Slow Access •RAM Access: any location (byte addressable) in memory accessed equally fast: hence “RAM.’ •Disks:–Data is organized along circular (concentric) circles•Tracks 000 to track 2999 for example (outer to inner)•Disks come in various architectures •Some have different storage capacities in different tracks. –Called constant angular velocity and constant linear velocity disks! LOOK UP! •Traditional disks (CAV) have same number of bits/track; different densities! (Velocity of outer tracks is much greater than inner tracks)•Disk organization:–Concentric platters, access arm(s), rotational speeds, seek time, data transfer times, etc.–Disk Controllers – small computers executing disk commands; shift registers, etc.6Disk Access – Four Key Components1. Seek time–Movement of access arm to correct cylinder–The most significant factor in access–May take 20 msec•2. Head Select – electronic speeds; negligible; fastest component•3. Rotational Delay – half speed of rotation; maybe 5-10 msec•4. Data Transfer – pretty quick too; –Tracks divided into fixed-sized sectors. Sector size predetermined at factory. (Some are marked as defective.)•Disk access times of 10 or less msec are common.•Important to note: disk access times are being reduced all the time, but so are main memory access time – and at a faster rate. Book points out that the disparity continues to grow!7Sequential File Organization and Access•Looking for a specific record in a sequential file:–While one can search for a specific record in a sequential file, for a large file, this is very painful. –This is called sequential access. – –Individual record searches are NOT practical, but can be done.– Entire file might need to be searched!–File is organized sequentially.–8More on Sequential Files•Sequential files are great for reporting, printing / displaying information, etc., but not for on-line retrieval of records!!•Insertions? Book does a poor job here.–While it is true that conceptually inserting a record into an existing file would require all records to be ‘moved’ forward (assuming the blocks are full), in practice this is often NOT done because the file would not be available for online access during this physical update!•Sequential files are NOT USED for online processing.•Transactions may be batched up during the day and the file is typically updated one time and offline –(Note: no one can access the file during updating) prior to generating end-of-day reports, exception reporting, summary reports, inventory reports, sales reports, statistical reports, listings, etc. if required...9Still More on Sequential Files•Need quick retrieval? Sequential Files won’t cut it.•If we have a need for near immediate response time –we need a different kind of file organization – one that provides for fast access too. (These go together) Sequential Files are super – for the right purposes.–Payroll, budgets, listings, rosters, accounts receivable, payables, inventories, hosts and hosts of items ––but NOT any kind of on-line processing (retrieval, updates) –Can hold tremendous amounts of data.–Often used for backup as well as master files.10B-Trees and Indexing•Overall objective of B-Trees and similar indexing schemes is to support: –Fast search–Fast insertion  External Files–Fast deletion–Fast access11B-Trees•Need a different kind of tree than 2-3-4 trees.•2-3-4 trees:–Fine for in-memory operations, but volume and persistency needs limit the applicability to large files.•For large files we need more data items (records) per node so when we retrieve them from disk, we retrieve into RAM (and store to disk) more records / block. •Idea is to have few disk retrievals (much time) and then do sequential