Today I Learned
  • Today I Learned
  • Database
    • Intro to Database Systems
      • Advanced SQL
      • Database Storage
        • Disk oriented Architecture
        • Storage Hierarchy
        • Disk-oriented DBMS
        • Why not use the OS?
        • Storage manager
        • Database Pages
        • Record IDs
        • Tuple layout
      • Database storage II
        • Log-structured file organization
        • Tuple storage
        • Postgres: numeric
        • Large value
        • External value storage
        • System catalogs
        • Observation
        • OLTP
        • OLAP
        • N-ARY STORAGE MODEL (NSM)
        • Decomposition storage model (DSM)
        • Tuple Identification
      • Buffer Pool & Memory management
        • Buffer pool organization
        • Buffer pool meta-data
        • Page Table vs. Page Directory
        • Allocation Polocies
        • Buffer Pool Optimizations
          • Multiple Buffer Pools
          • Pre-Fetching
          • Scan Sharing
        • Buffer Pool Bypass
        • OS Page Cache
        • Buffer Replacement Policies
        • Least-Recently Used
        • Clock
        • Problems
        • Better Policies: LRU-K
        • Better Policies: Localization
        • Better Policies: Priority Hints
        • Dirty Pages
        • Background Writing
      • Hash Table
        • Hash tables
          • Chain hashing
          • Extendible hashing
          • Linear hashing
      • Tree indexes I
        • Table indexes
        • B+ Tree
          • Properties
          • Nodes
        • B-Tree vs. B+Tree
        • Cluster indexes
        • Selection conditions
        • Node size
        • Merge threshold
        • Non-Unique indexes
        • Intra-node search
        • Prefix compression
        • Suffix truncation
        • Bulk insert
        • Pointer swizziling
      • Tree Indexes II
        • B+Tree: Duplicate Keys
        • Implicit Indexes
        • Partial Indexes
        • Covering Indexes
        • Index Include Columns
        • Functional/Expression Indexes
        • Observation
        • Trie Index
          • Trie Index Properties
          • Trie key span
          • Radix Tree
          • Observation
        • Inverted Index
        • Query Types
        • Design decisions
      • Multi-Threaded Index Concurrency Control
        • Locks vs. Latches
        • Latch modes
        • Latch implementations
        • Hash table latching
        • B+ Tree concurrency control
        • Latch crabbing/coupling
        • Leaf node scans
        • Page 5
      • Sorting & Aggregations
        • External Merge Sort
          • 2-Way External Merge Sort
        • Using B+ Trees For Sorting
          • Case #1 - Clustered B+ Tree
          • Case #2 - Unclustered B+ Tree
        • Aggragations
          • Sorting aggregation
          • Alternatives to sorting
          • Hashing aggregate
  • Back-end
    • Docker
      • Basic cmd
    • Network
      • The internet
        • Protocol Stacks and Packets
        • Networking Infrastructure
        • Internet Infrastructure
        • The Internet Routing Hierarchy
        • Application Protocols: HTTP and the World Wide Web
        • Transmission Control Protocol
        • Internet Protocol
    • Programming Languages
      • Compiled vs Interpreted
  • Personal
    • Reflections on the Tiny Things I Learned in
      • 2023
Powered by GitBook
On this page
  1. Database
  2. Intro to Database Systems
  3. Tree Indexes II
  4. Trie Index

Observation

The tree indexes that we've discussed so far are useful for "point" and "range" queries:

  • Find all customers in the 15217 zip code.

  • Find all orders between June 2018 and September 2018

They are not good at keyword searches:

  • Find all Wikipedia articles that contain the word "Pavlo"

PreviousRadix TreeNextInverted Index

Last updated 2 years ago