Lesson 3.1: B-Tree Architecture Deep Dive
Introduction
Indexes are the difference between a 10ms query and a 10-second query. Between a system that handles 1000 requests/second and one that crashes at 10.
For AI applications, indexing becomes even more critical:
- RAG systems query millions of embeddings
- Feature stores serve 10k+ reads/second
- Model logs grow to billions of rows
- Real-time inference can't wait for slow queries
How B-Trees Actually Work
Node structure:
[Page Header: 24 bytes]
[Item Pointers: N × 4 bytes]
[Free Space]
[Items: Key-Value pairs]
[Special Space: btree metadata]
Default page size: 8KB (8192 bytes)
Typical keys per page: 100-300
Tree height for 1B rows: 4-5 levels
Example: Index on email (TEXT column)
CREATE INDEX users_email_idx ON users(email);
-- Index entry format:
-- ['alice@example.com' → TID(page=42, offset=3)]
-- ['bob@example.com' → TID(page=42, offset=7)]
-- ...
-- TID = Tuple Identifier (pointer to heap row)
Index Scan Performance
Best case: Index Seek (single value)
SELECT * FROM users WHERE email = 'alice@example.com';
-- I/O operations:
-- 1. Read root page (usually cached)
-- 2. Read internal page (usually cached)
-- 3. Read leaf page (index)
-- 4. Read heap page (actual row)
-- Total: ~4 page reads (32KB) = 1-2ms
Range scan:
SELECT * FROM users WHERE created_at > NOW() - INTERVAL '7 days';
-- If index on created_at:
-- 1-2. Traverse B-tree to starting point
-- 3. Sequential scan through leaf pages
-- 4. Random heap reads for each row
-- Performance depends on result size
When indexes hurt performance:
-- Bad: Returning 50% of table
SELECT * FROM users WHERE status = 'active'; -- If 50% are active
-- Planner will choose Seq Scan instead of Index Scan
-- Why? Reading 500k random heap pages slower than reading entire table sequentially
Rule of thumb:
- Index Scan: Fast for under ~5% of table
- Bitmap Index Scan: Good for 5-25% of table
- Sequential Scan: Better for over 25% of table
Index Size and Maintenance
-- Check index size
SELECT
indexname,
pg_size_pretty(pg_relation_size(indexname::regclass)) AS size
FROM pg_indexes
WHERE tablename = 'documents';
-- Example output:
-- documents_pkey | 214 MB
-- documents_user_id_idx | 85 MB
-- documents_embedding_idx | 4.2 GB (vector index is large!)
Index bloat:
-- Rebuild bloated index
REINDEX INDEX documents_user_id_idx;
-- Or rebuild all indexes on table
REINDEX TABLE documents;
Key Takeaways
- B-tree nodes match disk page size (8KB) for optimal I/O
- Tree height stays small even with billions of rows (4-5 levels)
- Index seeks require ~3-4 page reads (1-2ms typical)
- Indexes are counterproductive when returning >25% of table rows
- Monitor index size and rebuild to fix bloat
- Understanding physical structure helps predict query performance
التالي · الدرس 16 من 45
Covering Indexes (Index-Only Scans)
قراءة 1 دقيقة
أنهيت 15 من 45 درسًا

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

