Chapter 4: Storage and Retrieval

Reference 1 in Chapter 4: How Partial, Covering, and Multicolumn Indexes May Slow Down UPDATEs in PostgreSQL

Nikolay Samokhvalov

2021

postgres.ai

Reference 2 in Chapter 4: Modern B-Tree Techniques

Goetz Graefe

Foundations and Trends in Databases 2011

web.archive.org PDF doi

Reference 3 in Chapter 4: Why Databases Use Ordered Indexes but Programming Uses Hash Tables

Evan Jones

2019

evanjones.ca

Reference 4 in Chapter 4: CEP-25: Trie-Indexed SSTable Format

Branimir Lambov

2022

cwiki.apache.org

Reference 5 in Chapter 4: Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

2009

Reference 6 in Chapter 4: Trie Memtables in Cassandra

Branimir Lambov

Proceedings of the VLDB Endowment 2022

vldb.org PDF doi

Reference 7 in Chapter 4: The History of RocksDB

Dhruba Borthakur

2013

rocksdb.blogspot.com

Reference 8 in Chapter 4: Apache HBase I/O—HFile

Matteo Bertozzi

2012

blog.cloudera.com

Reference 9 in Chapter 4: Bigtable: A Distributed Storage System for Structured Data

Fay Chang, Jeffrey Dean, Sanjay Ghemawat and 6 others

7th USENIX Symposium on Operating System Design and Implementation 2006

research.google

Reference 10 in Chapter 4: The Log-Structured Merge-Tree (LSM-Tree)

Patrick O'Neil, Edward Cheng, Dieter Gawlick and Elizabeth O'Neil

Acta Informatica 1996

cs.umb.edu PDF doi

Reference 11 in Chapter 4: The Design and Implementation of a Log-Structured File System

Mendel Rosenblum and John K. Ousterhout

ACM Transactions on Computer Systems 1992

research.cs.wisc.edu PDF doi

Reference 12 in Chapter 4: Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores

Michael Armbrust, Tathagata Das, Liwen Sun and 18 others

Proceedings of the VLDB Endowment 2020

vldb.org PDF doi

Reference 13 in Chapter 4: Space/Time Trade-offs in Hash Coding with Allowable Errors

Burton H. Bloom

Communications of the ACM 1970

people.cs.umass.edu PDF doi

Reference 14 in Chapter 4: Less Hashing, Same Performance: Building a Better Bloom Filter

Adam Kirsch and Michael Mitzenmacher

Random Structures & Algorithms 2008

eecs.harvard.edu PDF doi

Reference 15 in Chapter 4: Bloom Filter Calculator

Thomas Hurst

2023

hur.st

Reference 16 in Chapter 4: LSM-Based Storage Techniques: a Survey

Chen Luo and Michael J. Carey

The VLDB Journal 2019

arxiv.org doi

Reference 17 in Chapter 4: Dissecting, Designing, and Optimizing LSM-Based Data Stores

Subhadeep Sarkar and Manos Athanassoulis

ACM International Conference on Management of Data 2022

youtube.com

Reference 18 in Chapter 4: Name That Compaction Algorithm

Mark Callaghan

2018

smalldatum.blogspot.com

Reference 19 in Chapter 4: Embedded Databases (1): The Harmony of DuckDB, KùzuDB and LanceDB

Prashanth Rao

2023

thedataquarry.com

Reference 20 in Chapter 4: Bluesky Migrates to Single-Tenant SQLite

Hacker News discussion

2023

news.ycombinator.com

Reference 21 in Chapter 4: Organization and Maintenance of Large Ordered Indices

Rudolf Bayer and Edward M. McCreight

1970

dl.acm.org doi

Reference 22 in Chapter 4: The Ubiquitous B-Tree

Douglas Comer

ACM Computing Surveys 1979

web.archive.org PDF doi

Reference 23 in Chapter 4: Torn Write Detection and Protection

Alex Miller

2025

transactional.blog

Reference 24 in Chapter 4: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging

C. Mohan and Frank Levine

ACM International Conference on Management of Data 1992

ics.uci.edu PDF doi

Reference 25 in Chapter 4: The Internals of PostgreSQL

Hironobu Suzuki

2017

interdb.jp

Reference 26 in Chapter 4: LDAP at Lightning Speed

Howard Chu

Build Stuff '14 2014

buildstuff14.sched.com

Reference 27 in Chapter 4: Designing Access Methods: The RUM Conjecture

Manos Athanassoulis, Michael S. Kester, Lukas M. Maas and 4 others

19th International Conference on Extending Database Technology 2016

openproceedings.org PDF doi

Reference 28 in Chapter 4: Log Structured Merge Trees

Ben Stopford

2015

benstopford.com

Reference 29 in Chapter 4: The Advantages of an LSM vs. a B-Tree

Mark Callaghan

smalldatum.blogspot.co.uk 2016

smalldatum.blogspot.com

Reference 30 in Chapter 4: SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores

Oana Balmau, Florin Dinu, Willy Zwaenepoel and 3 others

USENIX Annual Technical Conference 2019

usenix.org

Reference 31 in Chapter 4: RocksDB Tuning Guide

Igor Canadi, Siying Dong, Mark Callaghan and et al

2023

github.com

Reference 32 in Chapter 4: What Modern NVMe Storage Can Do, and How to Exploit It: High-Performance I/O for High-Performance Storage Engines

Gabriel Haas and Viktor Leis

Proceedings of the VLDB Endowment 2023

vldb.org PDF doi

Reference 33 in Chapter 4: Coding for SSDs

Emmanuel Goossaert

2014

codecapsule.com

Reference 34 in Chapter 4: Is Sequential IO Dead in the Era of the NVMe Drive?

Jack Vanlightly

2023

jack-vanlightly.com

Reference 35 in Chapter 4: Storage System Design Analysis: Factors Affecting NVMe SSD Performance (2)

Alibaba Cloud Storage Team

2019

alibabacloud.com

Reference 36 in Chapter 4: The Fundamental Limit of Flash Random Write Performance: Understanding, Analysis and Performance Modelling

Xiao-Yu Hu and Robert Haas

2010

dominoweb.draco.res.ibm.com PDF gone archived copy

Reference 37 in Chapter 4: WiscKey: Separating Keys from Values in SSD-Conscious Storage

Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau and Remzi H. Arpaci-Dusseau

4th USENIX Conference on File and Storage Technologies 2016

usenix.org PDF

Reference 38 in Chapter 4: Innodb Double Write

Peter Zaitsev

2006

percona.com

Reference 39 in Chapter 4: On the Impact of Full-Page Writes

Tomas Vondra

2016

2ndquadrant.com

Reference 40 in Chapter 4: Read, Write & Space Amplification—B-Tree vs. LSM

Mark Callaghan

2015

smalldatum.blogspot.com

Reference 41 in Chapter 4: Choosing Between Efficiency and Performance with RocksDB

Mark Callaghan

Code Mesh 2016

youtube.com

Reference 42 in Chapter 4: Enabling Timely and Persistent Deletion in LSM-Engines

Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis and 2 others

ACM Transactions on Database Systems 2023

subhadeep.net PDF doi

Reference 43 in Chapter 4: Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication

Lukas Fittl

2025

pganalyze.com

Reference 44 in Chapter 4: How Postgres Stores Data on Disk—This One's a Page Turner

Drew Silcock

2024

drew.silcock.dev

Reference 45 in Chapter 4: Using Covering Indexes to Improve Query Performance

Joe Webb

simple-talk.com 2008

red-gate.com

Reference 46 in Chapter 4: The End of an Architectural Era (It’s Time for a Complete Rewrite)

Michael Stonebraker, Samuel Madden, Daniel J. Abadi and 3 others

33rd International Conference on Very Large Data Bases 2007

vldb.org PDF

Reference 47 in Chapter 4: VoltDB Technical Overview White Paper

2017

voltactivedata.com PDF

Reference 48 in Chapter 4: Log-Structured Memory for DRAM-Based Storage

Stephen M. Rumble, Ankita Kejriwal and John K. Ousterhout

12th USENIX Conference on File and Storage Technologies 2014

usenix.org PDF

Reference 49 in Chapter 4: OLTP Through the Looking Glass, and What We Found There

Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden and Michael Stonebraker

ACM International Conference on Management of Data 2008

hstore.cs.brown.edu PDF doi

Reference 50 in Chapter 4: Enhancements to SQL Server Column Stores

Per-Åke Larson, Cipri Clinciu, Campbell Fraser and 8 others

ACM International Conference on Management of Data 2013

web.archive.org PDF gone doi

Reference 51 in Chapter 4: The SAP HANA Database—An Architecture Overview

Franz Färber, Norman May, Wolfgang Lehner and 4 others

IEEE Data Engineering Bulletin 2012

web.archive.org PDF

Reference 52 in Chapter 4: The Traditional RDBMS Wisdom Is (Almost Certainly) All Wrong

Michael Stonebraker

EPFL 2013

slideshot.epfl.ch gone

Reference 53 in Chapter 4: Cloud-Native Transactions and Analytics in SingleStore

Adam Prout, Szu-Po Wang, Joseph Victor and 8 others

ACM International Conference on Management of Data 2022

dl.acm.org doi

Reference 54 in Chapter 4: HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm

Tino Tereshko and Jordan Tigani

2016

cloud.google.com

Reference 55 in Chapter 4: The Road to Composable Data Systems: Thoughts on the Last 15 Years and the Future

Wes McKinney

2023

wesmckinney.com

Reference 56 in Chapter 4: C-Store: A Column-Oriented DBMS

Michael Stonebraker, Daniel J. Abadi, Adam Batkin and 11 others

31st International Conference on Very Large Data Bases 2005

vldb.org PDF

Reference 57 in Chapter 4: Dremel Made Simple with Parquet

Julien Le Dem

blog.x.com 2013

blog.twitter.com

Reference 58 in Chapter 4: Dremel: Interactive Analysis of Web-Scale Datasets

Sergey Melnik, Andrey Gubarev, Jing Jing Long and 4 others

36th International Conference on Very Large Data Bases 2010

vldb.org PDF doi

Reference 59 in Chapter 4: Understanding Record Shredding: Storing Nested Data in Columns

Joe Kearney

2016

joekearney.co.uk

Reference 60 in Chapter 4: A Shallow Survey of OLAP and HTAP Query Engines

Jamie Brandon

2023

scattered-thoughts.net

Reference 61 in Chapter 4: The Snowflake Elastic Data Warehouse

Benoit Dageville, Thierry Cruanes, Marcin Zukowski and 15 others

ACM International Conference on Management of Data 2016

dl.acm.org doi

Reference 62 in Chapter 4: Data Management for Data Science Towards Embedded Analytics

Mark Raasveldt and Hannes Mühleisen

10th Conference on Innovative Data Systems Research 2020

duckdb.org PDF

Reference 63 in Chapter 4: Pinot: Realtime OLAP for 530 Million Users

Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam and 8 others

ACM International Conference on Management of Data 2018

cwiki.apache.org PDF doi

Reference 64 in Chapter 4: Druid: A Real-Time Analytical Data Store

Fangjin Yang, Eric Tschetter, Xavier Léauté and 3 others

ACM International Conference on Management of Data 2014

cs-courses.mines.edu PDF doi

Reference 65 in Chapter 4: Deep Dive into Common Open Formats for Analytical DBMSs

Chunwei Liu, Anna Pavlenko, Matteo Interlandi and Brandon Haynes

Proceedings of the VLDB Endowment 2023

vldb.org PDF doi

Reference 66 in Chapter 4: An Empirical Evaluation of Columnar Storage Formats

Xinyu Zeng, Yulong Hui, Jiahong Shen and 3 others

Proceedings of the VLDB Endowment

vldb.org PDF doi

Reference 67 in Chapter 4: Lance v2: A Columnar Container Format for Modern Data

Weston Pace

2024

blog.lancedb.com

Reference 68 in Chapter 4: Nimble, A New Columnar File Format

Yoav Helfman

VeloxCon 2024

youtube.com

Reference 69 in Chapter 4: Apache Arrow: High-Performance Columnar Data Framework

Wes McKinney

CMU Database Group—Vaccination Database Tech Talks 2021

youtube.com

Reference 70 in Chapter 4: Python for Data Analysis*, 3rd edition

Wes McKinney

2022

learning.oreilly.com

Reference 71 in Chapter 4: The Design of InfluxDB IOx: An In-Memory Columnar Database Written in Rust with Apache Arrow

Paul Dix

CMU Database Group—Vaccination Database Tech Talks 2021

youtube.com

Reference 72 in Chapter 4: Building Columnar Compression for Large PostgreSQL Databases

Carlota Soto and Mike Freedman

2024

timescale.com

Reference 73 in Chapter 4: The Design and Implementation of Modern Column-Oriented Database Systems

Daniel J. Abadi, Peter Boncz, Stavros Harizopoulos and 2 others

Foundations and Trends in Databases 2013

cs.umd.edu PDF doi

Reference 74 in Chapter 4: Consistently Faster and Smaller Compressed Bitmaps with Roaring

Daniel Lemire, Gregory Ssi‐Yan‐Kai and Owen Kaser

Software: Practice and Experience 2016

arxiv.org PDF doi

Reference 75 in Chapter 4: An Entire Social Network in 1.6GB (GraphD Part 2)

Jaz Volpert

2024

jazco.dev

Reference 76 in Chapter 4: The Vertica Analytic Database: C-Store 7 Years Later

Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan and 4 others

Proceedings of the VLDB Endowment 2012

vldb.org PDF doi

Reference 77 in Chapter 4: Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask

Timo Kersten, Viktor Leis, Alfons Kemper and 3 others

Proceedings of the VLDB Endowment 2018

vldb.org PDF doi

Reference 78 in Chapter 4: Memory Bandwidth Napkin Math

Forrest Smith

2020

forrestthewoods.com

Reference 79 in Chapter 4: MonetDB/X100: Hyper-Pipelining Query Execution

Peter Boncz, Marcin Zukowski and Niels Nes

2nd Biennial Conference on Innovative Data Systems Research 2005

cidrdb.org PDF

Reference 80 in Chapter 4: Implementing Database Operations Using SIMD Instructions

Jingren Zhou and Kenneth A. Ross

ACM International Conference on Management of Data 2002

www1.cs.columbia.edu PDF doi

Reference 81 in Chapter 4: OLTP Queries: Transfer Expensive Workloads to Materialize

Kevin Bartley

2024

materialize.com

Reference 82 in Chapter 4: Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals

Jim Gray, Surajit Chaudhuri, Adam Bosworth and 5 others

Data Mining and Knowledge Discovery 2007

arxiv.org PDF doi

Reference 83 in Chapter 4: Integrating the UB-Tree into a Database System Kernel

Frank Ramsak, Volker Markl, Robert Fenk and 3 others

26th International Conference on Very Large Data Bases 2000

vldb.org PDF

Reference 84 in Chapter 4: Bkd-Tree: A Dynamic Scalable kd-Tree

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge and Jeffrey Scott Vitter

8th International Symposium on Spatial and Temporal Databases 2003

users.cs.duke.edu PDF doi

Reference 85 in Chapter 4: Generalized Search Trees for Database Systems

Joseph M. Hellerstein, Jeffrey F. Naughton and Avi Pfeffer

21st International Conference on Very Large Data Bases 1995

dsf.berkeley.edu PDF

Reference 86 in Chapter 4: H3: Uber’s Hexagonal Hierarchical Spatial Index

Isaac Brodsky

2018

eng.uber.com gone archived copy

Reference 87 in Chapter 4: HyperDex: A Distributed, Searchable Key-Value Store

Robert Escriva, Bernard Wong and Emin Gün Sirer

ACM SIGCOMM Conference 2012

cs.princeton.edu PDF doi

Reference 88 in Chapter 4: Introduction to Information Retrieval

Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze

nlp.stanford.edu/IR-book 2008

nlp.stanford.edu

Reference 89 in Chapter 4: An Experimental Study of Bitmap Compression vs. Inverted List Compression

Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou and Steven Swanson

ACM International Conference on Management of Data 2017

cseweb.ucsd.edu PDF doi

Reference 90 in Chapter 4: What Is in a Lucene Index?

Adrien Grand

Lucene/Solr Revolution 2013

speakerdeck.com

Reference 91 in Chapter 4: Visualizing Lucene's Segment Merges

Michael McCandless

2011

blog.mikemccandless.com

Reference 92 in Chapter 4: Understanding Postgres GIN Indexes: The Good and the Bad

Lukas Fittl

2021

pganalyze.com

Reference 93 in Chapter 4: The State of (Full) Text Search in PostgreSQL 12

Jimmy Angelakos

FOSDEM 2020

youtube.com

Reference 94 in Chapter 4: Index Support for Regular Expression Search

Alexander Korotkov

PGConf.EU Prague 2012

wiki.postgresql.org PDF

Reference 95 in Chapter 4: Lucene's FuzzyQuery Is 100 Times Faster in 4.0

Michael McCandless

2011

blog.mikemccandless.com

Reference 96 in Chapter 4: Burst Tries: A Fast, Efficient Data Structure for String Keys

Steffen Heinz, Justin Zobel and Hugh E. Williams

ACM Transactions on Information Systems 2002

web.archive.org PDF doi

Reference 97 in Chapter 4: Fast String Correction with Levenshtein Automata

Klaus U. Schulz and Stoyan Mihov

International Journal on Document Analysis and Recognition 2002

dmice.ohsu.edu PDF doi

Reference 98 in Chapter 4: Efficient Estimation of Word Representations in Vector Space

Tomas Mikolov, Kai Chen, Greg Corrado and Jeffrey Dean

arXiv 2013

arxiv.org PDF

Reference 99 in Chapter 4: BERT: Pre-Training of Deep Bidirectional Transformers for Language Understanding

Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova

Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies 2019

arxiv.org PDF doi

Reference 100 in Chapter 4: Improving Language Understanding by Generative Pre-Training

Alec Radford, Karthik Narasimhan, Tim Salimans and Ilya Sutskever

openai.com 2018

cdn.openai.com PDF

Reference 101 in Chapter 4: Faiss Indexes

Matthijs Douze, Maria Lomeli and Lucas Hosseini

2024

github.com

Reference 102 in Chapter 4: Understanding pgvector's HNSW Index Storage in Postgres

Varik Matevosyan

2024

lantern.dev

Reference 103 in Chapter 4: Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors

Dmitry Baranchuk, Artem Babenko and Yury Malkov

European Conference on Computer Vision 2018

arxiv.org PDF doi

Reference 104 in Chapter 4: Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs

Yury A. Malkov and Dmitry A. Yashunin

IEEE Transactions on Pattern Analysis and Machine Intelligence 2020

arxiv.org PDF doi