blueprints
The database manages the disk data and buffers itself, not through the operating system (Os is not your friend.）。
three-level view
Database to page (page) as the basic unit of data storage, the file (file) is a series of pages of the collection, the page in the storage of page data (data), the formation of theFile-Page-DataThree-tier architecture.
Files are organized in different ways. Pages contain page headers and page data, and page data can be organized in different ways: tuples, logs, indexes.
The yellow sections are those that will be mentioned in the course.
Execution diagram when using Heapfile for file storage:
- Page catalog: stores meta information about managed pages (free pages, empty pages)
- Header: stores meta information about the page (page size, checksum, database version, transaction visibility, compression metadata)
Tuple-oriented data storage
-
Locate a pointer to the tuple (disk address) by <FileId, PageId, Slot> and then find the tuple.
-
Flexibility of slot pointers: no external awareness when internal tuple position changes; pointers can point to other pages, can store large data (files, large text); support for variable-length records.
-
The database assigns each tuple a data record identifier to indicate the tuple'sphysical locationROWID in SQLite and Oracle, CTID, <PageId, Slot> in Pg. But they are useless for the application.
-
Header contains: visibility information; NULL Bit Map.
-
Data contains: rows of data.
Tuple is just a string (char[]) and does not store type information itself; type information exists in the database'sSystem CatalogsMedium. (To keep the data compact; non-self-interpreting)
Problems encountered when storing data:
- Data alignment: padding, reordering
- Precision value problem: BIGDECIMAL (converted to string storage)
-
Null: Bit Map; special values
-
Large values and files: Overflow Page and External File.
Overflow pages are used for large values; large files can either use overflow pages or be stored on an external file system, which then stores a pointer to the path to the file rather than storing the file contents directly (Oracle: BFILE, Microsoft: FILESTREAM).
Log Structure Storage
Basic Concepts:
- Favor writing against reading, non-in-place updates: only PUT and DELETE operations, sequential IO. query the log from newest to oldest when querying.
- Accelerating queries: indexing.
- Accelerated query: log compression, and the log will be sorted when compressed.
- Compression: Hierarchical compression, unified compression
| specificities | Level Compaction | Universal Compaction |
|---|---|---|
| hierarchy | There are multiple levels, L0, L1, L2, etc. | No hierarchical structure, all documents at the same level |
| Organization of the document | No overlap of documents within each tier, gradual push down across tiers | Merge based on file size and volume, files may overlap |
| merger strategy | Cascading compression, sequential downward consolidation | Merge triggered when the number and size of files exceeds thresholds |
| zoom in | Higher because of the need to constantly push down documents to lower levels | Lower owing to less frequent consolidation |
| read magnification | is lower because the same key exists only once at each layer | Higher, as there is no strict hierarchy and multiple documents need to be examined |
| Applicable Scenarios | Scenes of reading more and writing less | High write scenarios with more writes and less reads and real-time data |
Indexed Organized Storage
Organize data directly with indexes, data hangs on leaf nodes, and tuples inside the Page are ordered.
SQLite and MySQL organize data this way by default, and Oracle and SQL Server optionally.
Comparison with tuple-based storage:
| characterization | Index-Organized Storage | Tuple-Oriented Storage |
|---|---|---|
| Data and Index Storage | Data is stored in a primary key index structure | Separate storage for data and indexes |
| data sorting | Data is sorted in primary key order | Unorganized data storage |
| Primary Key Query Performance | Efficient, as data is sorted by primary key | Dependent on primary key index, but the data itself is unordered |
| Insert and Update Performance | Index rearrangement may be required for insertion and update, slower | Faster inserts and updates, no need for primary key sorting |
| Applicable Scenarios | Scenarios with frequent primary key queries and highly sequential data | Multiple query modes for frequent insertion and update scenarios |