Historical Context - Library Organization

• Multiple ways to organize books: alphabetically by author/title, by subject, by spine color
• Bookstore example: sorting by color useful when customers remember "red book"
• Pre-1876: libraries ordered books by purchase date
  • New books allocated to shelves/boxes by size
  • Central card file listed locations
  • Required asking librarian for retrieval
  • No shelf browsing possible

Dewey Decimal System (1876)

• Melville Dewey published 4-page pamphlet on public library organization
• Assigned index numbers to subjects
• Shelves ordered by numerical system
• Became standard over years
• Solved information sorting/finding problem without bothering head librarian
• Enabled subject-based browsing
• Side note: Dewey was terrible person
  • Resigned from American Library Association in 1905 due to sexual harassment complaints
  • Sexist/racist biases affected early system versions
  • Many libraries now use different classifications

Computer Search Methods

• Two basic types: linear and binary search
• Example: stack of cards numbered 1-50, finding number 13

Linear Search

• Shuffled stack requires checking every card sequentially
• Works on any list in any order
• Usually slow performance

Binary Search

• Requires sorted/ordered data
• Split list in half, check middle item
• Eliminate half based on higher/lower comparison
• Repeat process until target found or confirmed absent
• With 11 cards: minimal difference vs linear
• With million cards: lightning fast vs linear

Database Complexity and Indexing

• Cards with multiple properties: numbers, letters, colors
• Can only sort by one property at a time
• Binary search only works for sorted property
• Other properties require linear search through entire list

Clustered Index

• Physically rearranging data on hard disk
• Like dictionary in alphabetical order
• Optimized for primary usage pattern

Non-Clustered Index

• Separate storage like book index or library catalog
• Stores specific property in simple, accessible format
• Process: binary search through index → identify card number → binary search to locate card
• Multiple property searches: pull from color index, note numbers, retrieve specific cards
• No linear search required anywhere

Performance Impact

• Minimal difference with 11 cards
• Dramatic difference with thousands/millions/billions of records
• Difference between hours vs fraction of second response time

Index Management Trade-offs

• Each index requires creation time and storage space
• Examples: Windows indexing service, Mac Spotlight search
• Systems index file properties for fast search responses
• Database changes require index updates
• Skill required in choosing which database fields to index
• Infrequent searches (once/twice yearly) may not justify indexing
• Computer science trade-off: space vs time

Google Search Example

• Full search index: 100 petabytes
• Customizes results for every user
• Usually responds under 1 second
• Despite changes: knowledge boxes, ads, optimization
• Still displays query response time on desktop results
• Represents advanced logistics and computer science
• PhD-level complexity, high-salary trade secrets
• Long evolution from Dewey decimal to Google search
• Same basic principle: create an index