Lesson 2.2: B-Trees and Hash Indexes
The Fundamental Data Structure: B-Tree
B-trees are the reason databases are fast. Understanding them is critical.
What is a B-Tree?
A balanced tree structure that keeps data sorted and allows searches, insertions, and deletions in O(log n) time.
Structure:
[50 | 100] ← Root (level 0)
/ | \
/ | \
[10|20|30] [60|70] [110|120] ← Internal nodes (level 1)
/ | | \ / | \ / | \
[...rows...] [...rows...] [...] ← Leaf nodes (level 2, actual data pointers)
Key properties:
- Each node has multiple keys (typically 100-1000)
- Tree height stays small (4 levels = 1 billion rows)
- Nodes are sized to match disk pages (8KB in Postgres)
Example: Finding id = 75
1. Read root node: [50 | 100] → Go right (75 > 50, 75 < 100)
2. Read node: [60 | 70] → Go right (75 > 70)
3. Read leaf node → Find row
Total disk reads: 3 (usually all cached after first query)
Index Types in PostgreSQL
B-Tree Index (Default)
-- Create index
CREATE INDEX users_email_idx ON users(email);
-- How it works
-- Index stores: [email → row_location]
-- Sorted: 'alice@...' → 'bob@...' → 'charlie@...'
-- Fast queries
SELECT * FROM users WHERE email = 'alice@example.com'; -- Index seek
SELECT * FROM users WHERE email LIKE 'alice%'; -- Index range scan
SELECT * FROM users ORDER BY email LIMIT 10; -- Index ordered scan
-- Slow queries (can't use index)
SELECT * FROM users WHERE email LIKE '%alice%'; -- Full table scan
Hash Index
-- Create hash index
CREATE INDEX users_email_hash_idx ON users USING HASH(email);
-- Use cases
-- Only supports equality (=), not ranges or LIKE
-- Slightly faster than B-tree for exact matches
-- Smaller index size
-- Fast
SELECT * FROM users WHERE email = 'alice@example.com';
-- Can't use hash index
SELECT * FROM users WHERE email > 'alice@example.com'; -- Needs ordering
When to use hash indexes:
- Equality lookups only (no ranges, no sorting)
- Very large text columns (UUIDs, hashes)
- Space-constrained environments
Most of the time, stick with B-tree.
How Indexes Speed Up Queries
Without index:
-- Full table scan
SELECT * FROM users WHERE email = 'alice@example.com';
-- Postgres scans every row (1 million rows)
-- Read all pages from disk: 8KB × 125,000 pages = 1GB read
-- Time: ~2-5 seconds
With index:
-- Index seek
CREATE INDEX users_email_idx ON users(email);
SELECT * FROM users WHERE email = 'alice@example.com';
-- Postgres:
-- 1. Reads 3-4 index pages (B-tree traversal)
-- 2. Gets row location
-- 3. Reads 1 heap page (actual row)
-- Total: 4-5 page reads = ~40KB
-- Time: 1-2ms (500x faster)
Key Takeaways
- B-trees keep data sorted and enable O(log n) searches
- B-tree height stays small even with billions of rows (typically 3-4 levels)
- B-tree indexes support equality, ranges, sorting, and prefix matching
- Hash indexes only support equality but are slightly faster for exact matches
- Indexes dramatically reduce disk I/O by avoiding full table scans
- Most queries should use B-tree indexes as the default choice
التالي · الدرس 12 من 45
Query Execution, Planner, and Optimizer
قراءة 2 دقيقة
أنهيت 11 من 45 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

