Data Models

1. What Is a Data Model?

• An abstraction layer between computers and the real world that describes the characteristics of data.

2. Why Do We Need Data Models?

• Computers cannot directly process real-world things. People must convert real-world things into digital data before computers can recognize and process them.

3. What Data Models Are There?

• Conceptual model: describes information in the real world.
• Logical model: data structures in memory or on disk.
• Physical model: byte streams serialized to disk or transmitted over a network.

4. Conceptual Models

4.1. Relational Model

• Data is organized into relations (tables), where each relation is an unordered set of tuples (rows).
• Relationships include one-to-one, one-to-many, and many-to-many.
• Suitable for join operations.

4.2. Document Model

• Stores data by document and supports arrays and nested documents. It can simply be understood as JSON.
• Does not enforce a schema on stored data.
• Suitable for one-to-many relationships where most records are unrelated to each other.

4.3. Graph Model

• A graph consists of two kinds of objects: vertices + edges.
• Does not enforce a schema on stored data.
• Suitable for many-to-many relationships where anything may be related to anything else.

5. Logical Models

• According to the use case, systems can be divided into OLAP and OLTP.

Attribute	Transaction Processing OLTP	Analytical Processing OLAP
Target users	End Web users	Internal data analysts
Real-time read/write requirement	High	Low
Transaction requirement	High	Low
Analysis requirement	Low, simple	High, complex
Data processed	Data at the current point in time	Historical events accumulated over time
Main read pattern	Query a small number of records by key	Aggregate over large batches of records
Main write pattern	Random access, low-latency writes	Batch import (ETL), event streams
Dataset size	GB ~ TB	TB ~ PB
Data-structure category	log-structured or page-oriented depending on read/write pattern	Column storage

• Whether data is stored on disk or in memory:
  • Because the data volume is large and according to Disk vs Memory (related note not yet public), disk must be used.
• Which data structure should be used?
  • It depends on the use case.

5.1. log-structured

5.1.1. Use Cases

• Transaction processing.
• More writes, fewer reads.

5.1.2. What Is It?

• Log: an append-only data file.
• It can be viewed as a K-V database.
• Sequential disk writes are efficient.
• To avoid running out of disk space, divide the log into segments of a fixed size. At certain times, compact segments and merge entries with the same key, removing old keys.
• How to handle large numbers of writes:
  • Sequential disk I/O.
• The same data occupies multiple copies of space:
  • Periodically merge and compact data in the background.
• One file or multiple files:
  • One file. Divide it by a fixed-size threshold and decide how data is merged.
• Loading files into memory, sorting, and then merging is inefficient:
  • Keep the data inside each file sorted.
• How to keep files sorted:
  • Sort on insertion.
• How to sort:
  • Red-black tree, skip list, B-tree.
• Sequential disk writes are still slow:
  • Buffer data in memory for a period of time, then write to disk in batches.
• How to avoid losing in-memory data:
  • redo log.
• How to read data:
  • Read from newest to oldest and stop once the data is found.
• Read optimization:
  • Add a Bloom Filter to each SSTable to quickly determine whether the requested data exists and accelerate reads.
  • Partition SSTables. Except for L0, data between levels does not overlap, and data within a level is stored in order.
  • Optimize compaction efficiency to prevent compaction from blocking reads.
• Three major problems:
  • Read amplification: reads need to search from newer values to older values, involving more than one I/O operation. This is especially obvious for range queries.
  • Space amplification: in an LSM Tree, all writes are append-based, so expired or deleted data is not cleaned up immediately and still occupies space.
  • Write amplification: background merging is generally used to reduce read and space amplification, but this introduces write amplification. It is the ratio between the actual amount of data written to disk and the amount of data the program asked to write. During compaction, one item may be written multiple times.

5.1.3. Implementation

• LSM

5.2. page-oriented

5.2.1. Use Cases

• Transaction processing.
• More reads, fewer writes.

5.2.2. What Is It?

• How to read and write disk quickly:
  • Sequential I/O.
• After appending every record sequentially, how do we read quickly?
  • Maintain an index for every record.
• An index for every record is too large:
  • Every record needs an index because records are variable-length.
    • Then make them fixed-length, for example divide the disk into fixed-size blocks.
    • Maintain indexes for records inside a block; use a number between blocks.
  • Block size: operating-system page.
  • Whether to store the block index: yes, either clustered (data and index together) or non-clustered.
• How to support sorting and range queries:
  • Sort data when writing.
• B+ tree vs B-tree:
  • B Tree
• Conclusion:
  • We found a data structure that can be maintained both on disk and in memory: the B+ tree. In memory, a B+ tree stores the data; each disk page corresponds to one node of the in-memory B+ tree (index pages map to non-leaf nodes and data pages map to leaf nodes).
  • Core reasons: low tree height, relatively few disk I/Os, and relatively even time complexity across requests.

5.2.3. Implementation

• MySQL Index Internals
• InnoDB redo log

5.3. Column Storage

5.3.1. Use Cases

• Analytical processing often reads many rows but only a few fields, so column-oriented storage is suitable.

5.3.2. What Is It?

• Instead of storing all values from one row together, store all values from each column together.
• Values in the same column are easier to compress, reducing a large amount of work.

6. Physical Models

• Serialization: convert an in-memory data structure into a byte sequence stored on disk or transmitted over a network.
• Deserialization: convert a byte sequence stored on disk or transmitted over a network into an in-memory data structure.

6.1. Text Formats

6.1.1. JSON

• JSON distinguishes strings and numbers, but does not distinguish integers and floating-point numbers, and cannot determine precision.
• Does not support binary strings.

6.1.2. XML

• Cannot distinguish a number from a string that happens to consist only of digits.
• Does not support binary strings.

6.1.3. CSV

• Cannot distinguish a number from a string that happens to consist only of digits.

6.2. Binary Formats

6.2.1. Thrift

6.2.2. ProtocolBuf

6.2.3. Avro

6.3. Text vs Binary

	Text	Binary
Advantages	Highly readable and self-describing	Compact messages; low parsing overhead
Disadvantages	Redundant messages; high parsing overhead	Poor readability

7. Data Query Languages

7.1. Imperative Query

• Give the machine detailed commands for how to do something in order to obtain the desired result (what).

7.2. Declarative Query

• Only state the desired result (what), and let the machine determine the process (how).

7.3. Map-Reduce Query

• Split a large batch of data for execution (Map), then merge the results into the final result (Reduce).

8. References

• What Is a Data Model?
• DDIA Chapter 2
• Imperative vs Declarative Programming
• Storage and Indexing — DDIA Notes
• DDIA Chapter 3
• OLAP and Data Warehouses — DDIA Notes
• Encoding and Schemas — DDIA Notes
• DDIA Chapter 4