Introduction to Database Systems
CMSC 23500 Section 1/2 (Rehman) Lecture 7 – Indexing I
Slides from Aaron Elmore, Andy Pavlo and Silberchatz et. al.
Agenda and Updates
• Database Indexes • B+Trees
• Reading:Chapter14.3
• CrustyDB 1: Page Milestone is Out
• Due Friday, 19th April at 11:59 am (Noon) • Final Grade Breakdown
Problem #2 Recap
• Suppose:
• We can hold 100 index entries per index page. • Index pages are 4 kilobytes (kb) = 4000 bytes. • 10ms to read a random block (tT+tS)
• Dense sorted index built on 1,000,000 tuples
• How many (binary) searches per second can you do on the index to find the RID (round down)?
Problem #2 Recap
Tuple 999,999
Index page holds 100 Index Entries / Page
10 ms random page read
Problem #2 Recap
Idx Page 0
Index page holds 100 Index Entries / Page
Indexing 1,000,000 tuples = 10,000 pages
10 ms random page read
Idx Page 1
Tuple 500,001
Tuple 500,002
Tuple 999,,90919
Tuple 999,999 Tuple 1M
Tuple 999,999 Tuple 1M
Problem #2 Recap
Index page holds 100 Index Entries / Page
Indexing 1,000,000 tuples = 10,000 pages
10 ms random page read
Binary search takes 140 ms =ceil(log2(10,000))*10
approx 14 page reads to locate a tuple How can we speed up?
Tuple 999,999 Tuple 1M
Tuple 999,999 Tuple 1M
Idx Page 0
Idx Page 1
Tuple 500,001
Tuple 500,002
Tuple 999,,90919
How can we speed up?
Idx Page 0
Idx Page 1
Tuple 500,001
Tuple 500,002
Tuple 999,,90919
Tuple 999,999 Tuple 999,999 Tuple 1M Tuple 1M
How can we speed up?
Idx Page 0.0
Idx Page 1.1
Idx Page 0.50
Tuple 500,001
1.5000 Tuple 500,001
Tuple 500,002
Idx Page 0.99
Tuple 990,001
Tuple 999,901
Tuple 9991,.90,9199
Sparse Index 1 entry per Idx Page
Tuple 999,999 Tuple 999,999 Tuple 1M Tuple 1M
Dense Index
Idx Page 1.0
How can we speed up?
Idx Page 1.0
Idx Page 3.1
Idx Page 0.0
Tuple 500,101
Tuple 990,001
Idx Page 1.50
Tuple 500,001
3.5000 Tuple 500,001
Tuple 500,002
Idx Page 1.99
Tuple 990,001
Tuple 999,901
Tuple 9993,.90,9199
Sparse Index 1 entry per Idx Page
Tuple 999,999 Tuple 999,999 Tuple 1M Tuple 1M
Dense Index
Idx Page 3.0
Code Help, Add WeChat: cstutorcs
How can we speed up?
Idx Page 1.0
Idx Page 3.1
Idx Page 0.0
Tuple 500,101
Tuple 990,001
Idx Page 1.50
Tuple 500,001
3.5000 Tuple 500,001
Tuple 500,002
Idx Page 1.99
Tuple 990,001
Tuple 999,901
Tuple 9993,.90,9199
Tuple 999,999 Tuple 999,999 Tuple 1M Tuple 1M
Idx Page 3.0
It’s a Tree!
Tuple 990,001
Tuple 500,101
Idx Page 0.0
Tuple 999,999
Tuple 999,901
Tuple 990,001
Idx Page 1.99
Tuple 500,001
Idx Page 1.50
Idx Page 1.0
Idx Page 3.0
Idx Page 3.1
Tuple 500,002
Tuple 500,001
Tuple 999,999
Tuple 9993,.90,9199
Programming Help, Add QQ: 749389476
(some slides for Dbsys and Tanu malik)
• An ordered tree that supports efficient equality and range look ups for disk (and memory) based systems.
• Is height-balancing (top to bottom is always the same)
• Workhorse of modern databases.
• Different but similar to B-Tree. We are only going to discuss B+.
Example of B+-Tree
Internal nodes
Leaf nodes
Srinivasan
Srinivasan
Srinivasan
Comp. Sci.
Comp. Sci.
Comp. Sci.
Elec. Eng.
Data entries
(Index File)
(Data file)
Data Records
Data Records
UNCLUSTERED
Note: can also store data records directly as data entries (primary index)
CSE 544 – Fall 2007
Data entries
• Parameter 𝒅 = the degree
• Eachnodehas𝑑≤𝑚≤ 2𝑑keys(exceptroot–itcanhavejustonekey)
𝑘 < 30 30 ≤ k < 120 120 ≤ k < 240 240 ≤ k
Each node also has 𝑚 + 1 pointers
• Eachleafhas𝑑≤ 𝑚≤ 2𝑑keys: Leaf
Pointers to Records in Pages
Searching a B+ Tree
• Exact key values:
– Start at the root
• Exact key values:
– Proceed down, to the leaf
• Start at the root
• Proceed down, to the leaf
• Range queries:
• Range queries:
– Find lowest bound as above
• Find lowest bound as above – Then sequential traversal
• Then sequential traversal
CSE 544 - Fall 2007
Select name From Student Where age = 25
Select name From Student Where 20 <= age
and age <= 30
Find Key 𝟒𝟎
20 < 𝟒𝟎 ≤ 60
30 < 𝟒𝟎 ≤ 40
20 30 40 50 60 65 80 85 90
Find Key ≥ 𝟒𝟎
20 < 𝟒𝟎 ≤ 60
30 < 𝟒𝟎 ≤ 40
20 30 40 50
60 65 80 85 90
Follow Leaf Pointers for all values ≥ 40
程序代写 CS代考 加QQ: 749389476
• How large can 𝑑 be?
• Example:
• Keysize= 4 bytes
• Pointer size = 8 bytes
• Page size = 4096 bytes
•2𝑑×4+ 2𝑑+1×8≤4096 • d = 170
B+ Trees in practice
• 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 pin the top levels in buffer pool • Level1=1page=4kb
• Level 2= 133 pages = 1Mbyte
• Level 3 = 17,689 pages = 133 Mbytes
Inserts and Deletes
• Find the Leaf where K belongs and insert into that leaf node • If Leaf does not overflow (≤ 2𝑑 keys), Stop
• Else, Split Node and insert middle value to parent
Insert / Split
If node is a leaf node, keep K3 also in right node. If root splits, root has only one key.
Insert 𝐾 = 19
Find Position for 𝑘 = 19
10 15 18 19 20 30 40 50 60 65 80 85 90
After Insertion
10 15 18 19 20 30 40 50 60 65 80 85 90
Now insert 𝐾 = 25
Find Position for 𝑘 = 25
10 15 18 19 20 30 40 50 60 65 80 85 90
Now insert 𝐾 = 25
Find Position for 𝑘 = 25
10 15 18 19 20 25 30 40 50 60 65 80 85 90
Now insert 𝐾 = 25
Overfull (5 > 2𝑑)
10 15 18 19 20 25 30 40 50 60 65 80 85 90
Split the Node
10 15 18 19 20 25 30 40 50 60 65 80 85 90
After Insertion and Split
10 15 18 19 20 25 30 40 50 60 65 80 85 90
Now what if I Delete 𝐾 = 30
10 15 18 19 20 25 30 40 50 60 65 80 85 90
Delete 𝐾 = 30
May Change to 40, or not
10 15 18 19 20 25 40 50 60 65 80 85 90
Now Delete 𝐾 = 25
10 15 18 19 20 25 40 50 60 65 80 85 90
Now Delete 𝐾 = 25
10 15 18 19 20 40 50 60 65 80 85 90
Now Delete 𝐾 = 25
Re-balance
10 15 18 19 20 40 50 60 65 80 85 90
Now Delete 𝐾 = 25
10 15 18 19 20 40 50 60 65 80 85 90
Now Delete 𝐾 = 40
10 15 18 19 20 40 50 60 65 80 85 90
Now Delete 𝐾 = 40
10 15 18 19 20 50 60 65 80 85 90
Now Delete 𝐾 = 40
Re-balance not possible
10 15 18 19 20 50 60 65 80 85 90
Now Delete 𝐾 = 40
Merge Nodes
10 15 18 19 20
50 60 65 80 85 90
Final Tree
After Merge
10 15 18 19 20
50 60 65 80 85 90
Complexity of Updates
• Cost (in terms of number of I/O operations) of insertion and deletion of a single entry proportional to height of the tree
• With 𝐾 entries and maximum fanout of 𝑛, worst case complexity of insert/delete of an entry is O(log 0 𝐾)
• In practice, number of I/O operations is less: • Internal nodes tend to be in buffer
• Splits/merges are rare, most insert/delete operations only affect a leaf node • Average node occupancy depends on insertion order
• !”rds with random, #! with insertion in sorted order
Unique Search Keys
• Alternatives to scheme described earlier • Buckets on separate block (bad idea)
• List of tuple pointers with each key
• Extracodetohandlelonglists
• Deletionofatuplecanbeexpensiveiftherearemanyduplicatesonsearch key (why?)
• Worst case complexity may be linear!
• Lowspaceoverhead,noextracostforqueries
• Make search key unique by adding a record-identifier • Extrastorageoverheadforkeys
• Simplercodeforinsertion/deletion
• Widelyused
Tree File Organization
• B+-Tree File Organization:
• Leaf nodes in a B+-tree file organization store
records, instead of pointers
• Helps keep data records clustered even when there are insertions/deletions/updates
• Leaf nodes are still required to be half full
• Since records are larger than pointers, the maximum number of records that can be stored in a leaf node is less than the number of pointers in a nonleaf node.
• Insertion and deletion are handled in the same way as insertion and deletion of entries in a B+-tree index.
Other Issues in Indexing
• Record relocation and secondary indices
• If a record moves, all secondary indices that store record pointers have to be
• Could point to PK instead of RID
Indexing Strings
• Variable length strings as keys
• Variable fanout
• Use space utilization as criterion for splitting, not number of pointers
• Prefix compression
• Key values at internal nodes can be prefixes of full key
• Keepenoughcharacterstodistinguishentriesinthesubtreesseparatedbythekey value
• E.g., “Silas” and “Silberschatz” can be separated by “Silb”
• Keys in leaf node can be compressed by sharing common prefixes
Bulk Loading and Bottom-Up Build
• Inserting entries one-at-a-time into a B+-tree requires 3 1 IO per entry
• assuming leaf level does not fit in memory
• can be very inefficient for loading a large number of entries at a time (bulk loading)
• Efficient alternative 1:
• sort entries first (using efficient external-memory sort algorithms discussed later in
Section 12.4)
• insert in sorted order
• insertionwillgotoexistingpage(orcauseasplit)
• muchimprovedIOperformance,butmostleafnodeshalffull
• Efficient alternative 2: Bottom-up B+-tree construction • As before sort entries
• And then create tree layer-by-layer, starting with leaf level
• detailsasanexercise
• Implemented as part of bulk-load utility by most database systems
Indices on Multiple Attributes
Suppose we have an index on combined search-key (dept_name, salary).
• Withthewhereclause
where dept_name = “Finance” and salary = 80000
the index on (dept_name, salary) can be used to fetch only records that satisfy both conditions.
• Using separate indices in less efficient — we may fetch many records (or pointers) that satisfy only one of the conditions.
• Can also efficiently handle
where dept_name = “Finance” and salary < 80000
• But cannot efficiently handle
where dept_name < “Finance” and balance = 80000
• May fetch many records that satisfy the first but not the second condition
Creation of Indices
create index takes_pk on takes (ID,course_ID, year, semester,
drop index takes_pk
• Most database systems allow specification of type of index, and clustering.
• Indices on primary key created automatically by all databases • Why?
• Some database also create indices on foreign key attributes • Why might such an index be useful for this query:
• takes ⨝ σname='Shankar' (student)
• Indices can greatly speed up lookups, but impose cost on updates
• Index tuning assistants/wizards supported on several databases to help choose indices, based on query and update workload
Index Definition in SQL
• Create an index
create index
(
• Use create unique index to indirectly specify and enforce the condition that the search key is a candidate key is a candidate key.
• Not really required if SQL unique integrity constraint is supported
• To drop an index
drop index
• Most database systems allow specification of type of index, and
clustering.
• create index
Next Lecture
• Database Indexes II
• Readings: Database System Concepts: Chapter 14.3