Consider the world’s simplest database, implemented as two bash functions:
- 05.01Storage and Indexing for OLTPConsider the world’s simplest database, implemented as two bash functions:
- 05.02Log-Structured StorageTo start, let’s assume that you want to continue storing data in the append-only file written by db_set, and you just want to speed up reads. One way you could do this is by…
- 05.03B-TreesThe log-structured approach is popular, but it is not the only form of key-value storage. The most widely used structure for reading and writing database records by key is the…
- 05.04Comparing B-Trees and LSM-TreesAs a rule of thumb, LSM-trees are better suited for write-heavy applications, whereas B-trees are faster for reads. However, benchmarks are often sensitive to details of the…
- 05.05Multicolumn and Secondary IndexesSo far we have discussed only key-value indexes, which are like primary-key indexes in the relational model. A primary key uniquely identifies one row in a relational table, or…
- 05.06Keeping Everything in MemoryThe data structures discussed so far in this topic have all been answers to the limitations of disks. Compared to main memory, disks are awkward to deal with. With both…
- 05.07Data Storage for AnalyticsThe data model of a data warehouse is most commonly relational, because SQL is generally a good fit for analytical queries. There are many graphical data analysis tools that…
- 05.08Cloud Data WarehousesEstablished data warehouse vendors such as Teradata, Vertica, and SAP HANA offer on-premises deployments under commercial licenses as well as cloud-based solutions. But as more…
- 05.09Column-Oriented StorageAs discussed in “Stars and Snowflakes: Schemas for Analytics”, data warehouses by convention often use a relational schema with a big fact table that contains foreign-key…
- 05.10Query Execution: Compilation and VectorizationA complex SQL query for analytics is broken down into a query plan consisting of multiple stages, called operators, which may be distributed across multiple machines for…
- 05.11Materialized Views and Data CubesWe previously encountered materialized views in “Materializing and Updating Timelines”: in a relational data model, they are table-like objects whose contents are the results…
- 05.12Multidimensional and Full-Text IndexesThe B-trees and LSM-trees we saw in the first half of this topic allow range queries over a single attribute; for example, if the key is a username, you can use them as an…
- 05.13Recap: Storage and RetrievalIn this topic we tried to get to the bottom of how databases perform storage and retrieval. What happens when you store data in a database, and what does the database do when…