DOC PREVIEW
UW CSE 444 - Indexes

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 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 35 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 35 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 35 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 35 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 35 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 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Lecture 21: IndexesOutlinePhysical AddressesLogical AddressesMain Memory AddressOptimization: Pointer SwizzlingPointer SwizzlingSlide 8Slide 9IndexesIndex ClassificationPrimary IndexSlide 13Primary Index with Duplicate KeysSlide 15Slide 16Secondary IndexesClustered/UnclusteredClustered vs. Unclustered IndexSlide 20Applications of Secondary IndexesComposite Search KeysB+ TreesB+ Trees BasicsB+ Tree ExampleB+ Tree DesignSearching a B+ TreeB+ Trees in PracticeInsertion in a B+ TreeSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Lecture 21: IndexesMonday, November 13, 2000Outline•Addresses (3.3)•Index Structures (4.1, 4.2, 4.3)Physical Addresses•Each block and each record have a physical address that consists of:–The host–The disk–The cylinder number–The track number–The block within the track–For records: an offset in the block•sometimes this is in the block’s headerLogical Addresses•Logical address: a string of bytes (10-16)•More flexible: can blocks/records around•But need translation table:Logical address Physical addressL1 P1L2 P2L3 P3Main Memory Address•When the block is read in main memory, it receives a main memory address•Need another translation tableMemory address Logical addressM1 L1M2 L2M3 L3Optimization: Pointer Swizzling•= the process of replacing a physical/logical pointer with a main memory pointer•Still need translation table, but subsequent references are fasterPointer SwizzlingDiskBlock 1Block 2Memoryread in memoryswizzledunswizzledPointer Swizzling•Automatic: when block is read in main memory, swizzle all pointers in the block•On demand: swizzle only when user requests•No swizzling: always use translation tablePointer Swizzling•When blocks return to disk: pointers need unswizzled•Danger: someone else may point to this block–Pinned blocks: we don’t allow it to return to disk–Keep a list of references to this blockIndexes•An index on a file speeds up selections on the search key fields for the index.–Any subset of the fields of a relation can be the search key for an index on the relation.–Search key is not the same as key (minimal set of fields that uniquely identify a record in a relation).•An index contains a collection of data entries, and supports efficient retrieval of all data entries with a given key value k.Index Classification•Primary/secondary•Clustered/unclustered•Dense/sparse•B+ tree / Hash table / …Primary Index•File is sorted on the index attribute•Dense index: sequence of (key,pointer) pairs10203040506070801020304050607080Primary Index•Sparse index10305070901101301501020304050607080Primary Index with Duplicate Keys•Dense index:10203040506070801010102020203040Primary Index with Duplicate Keys•Sparse index: pointer to lowest search key in each block:•Search for 20101020301010102020203040Primary Index with Duplicate Keys•Better: pointer to lowest new search key in each block:•Search for 2010203040506070801010102030304050Secondary Indexes•To index other attributes than primary key•Always dense (why ?)10102020203030302030302010201030Clustered/Unclustered•Primary indexes = usually clustered•Secondary indexes = usually unclusteredClustered vs. Unclustered IndexData entries(Index File)(Data file)Data RecordsData entriesData RecordsCLUSTEREDUNCLUSTEREDSecondary Indexes•Applications:–index other attributes than primary key–index unsorted files (heap files)–index clustered dataApplications of Secondary Indexes•Clustered dataCompany(name, city), Product(pid, maker)Select cityFrom Company, ProductWhere name=maker and pid=“p045”Select pidFrom Company, ProductWhere name=maker and city=“Seattle”Company 1 Company 2 Company 3Products of company 1Products of company 2 Products of company 3Composite Search Keys•Composite Search Keys: Search on a combination of fields.–Equality query: Every field value is equal to a constant value. E.g. wrt <sal,age> index:•age=20 and sal =75–Range query: Some field value is not a constant. E.g.:•age =20; or age=20 and sal > 10sue 13 75bobcaljoe 121020801112name age sal<sal, age><age, sal> <age><sal>12,2012,1011,8013,7520,1210,1275,1380,111112121310207580Data recordssorted by nameData entries in indexsorted by <sal,age>Data entriessorted by <sal>Examples of composite keyindexes using lexicographic order.B+ Trees•Search trees•Idea in B Trees:–make 1 node = 1 block•Idea in B+ Trees:–Make leaves into a linked list (range queries are easier)•Parameter d•Each node has >= d and <= 2d keys (except root)•Each leaf has >=d and <= 2d keys:B+ Trees Basics30 120 240Keys k < 30Keys 30<k<=120Keys 120<k<=240 Keys 240<k40 50 604050 60Next leafB+ Tree Example8020 60 100 120 14010 15 18 20 30 40 50 60 65 80 85 9010 15 18 20 30 40 50 60 65 80 85 90d = 2B+ Tree Design•How large d ?•Example:–Key size = 4 bytes–Pointer size = 8 bytes–Block size = 4096 byes•2d x 4 + (2d+1) x 8 <= 4096•d = 170Searching a B+ Tree•Exact key values:–Start at the root–Proceed down, to the leaf•Range queries:–As above–Then sequential traversalSelect nameFrom peopleWhere age = 25Select nameFrom peopleWhere 20 <= age and age <= 30B+ Trees in Practice•Typical order: 100. Typical fill-factor: 67%.–average fanout = 133•Typical capacities:–Height 4: 1334 = 312,900,700 records–Height 3: 1333 = 2,352,637 records•Can often hold top levels in buffer pool:–Level 1 = 1 page = 8 Kbytes–Level 2 = 133 pages = 1 Mbyte–Level 3 = 17,689 pages = 133 MBytesInsertion in a B+ TreeInsert (K, P)•Find leaf where K belongs, insert•If no overflow (2d keys or less), halt•If overflow (2d+1 keys), split node, insert in parent:•If leaf, keep K3 too in right node•When root splits, new root has 1 key onlyK1 K2 K3 K4 K5P0 P1 P2 P3 P4 p5K1 K2P0 P1 P2K4 K5P3 P4 p5(K3, ) to parentInsertion in a B+ Tree8020 60 100 120 14010 15 18 20 30 40 50 60 65 80 85 9010 15 18 20 30 40 50 60 65 80 85 90Insert K=19Insertion in a B+ Tree8020 60 100 120 14010 15 18 19 20 30 40 50 60 65 80 85 9010 15 18 20 30 40 50 60 65 80 85 9019After insertionInsertion in a B+ Tree8020 60 100 120 14010 15 18 19 20 30 40 50 60 65 80 85 9010 15 18 20 30 40 50 60 65 80 85 9019Now insert 25Insertion in a B+ Tree8020 60 100 120 14010 15 18 19 20 2530 4050 60 65 80 85 9010 15 18 20 25 30 40 60 65 80 85 9019After insertion50Insertion in a B+ Tree8020 60 100 120 14010 15 18 19 20 2530 4050 60 65 80 85 9010 15 18 20 25


View Full Document

UW CSE 444 - Indexes

Documents in this Course
XML

XML

48 pages

SQL

SQL

25 pages

SQL

SQL

42 pages

Recovery

Recovery

30 pages

SQL

SQL

36 pages

Security

Security

36 pages

Wrap-up

Wrap-up

6 pages

SQL

SQL

37 pages

More SQL

More SQL

48 pages

SQL

SQL

35 pages

XML

XML

46 pages

Triggers

Triggers

26 pages

Load more
Download Indexes
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 Indexes 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 Indexes 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?