关系型数据库如何检索数据
说实话研究数据库的底层对常见的项目帮助不大，或者说不受重视，更多是在业务编排上。数据库随便建建，增删改查随便写写，功能就完成了，项目就上线了。但程序员总要有些追求，并且数据库的细节知识很泛用。如 Schema、索引、数据结构、事务、锁，这些知识不止是数据库独有的，说是学习数据库，不如说是借由数据库来学习一下这些知识。不参透数据库设计，就像四大名著不读红楼梦，后面忘了…。
本文主要讨论关系型数据库，可能会顺带一提与 NoSql 相关的知识。
数据库的 Schema
数据库大多是通过索引、表、数据类型等特性管理数据。但对于关系型数据库来说，需要从强类型说起。强类型主要是降低调用方的负担，编译期间就会给出报错，将类型错误扼杀在生产之前，不过需要编写强类型的一方“负重前行”。不过大家都会在类型上偷点懒， typescript 经常会被戏称为 anyscript 似乎是个很好的例子。
所谓“负重”，其实就是我们使用 Schema （模式） 描述一个元素。Graphql 的接口定义是一个例子，关系型数据库更是如此。使用 Schema 描述表、列、索引、视图、以及外键约束各种关系等。不用钻研 Schema 是如何运作的，只需知道只有数据不会平白无故形成，为此你必须要提供一个 Schema 。
数据库是通过 Schema 实现对数据结构的高度控制（强类型）。进行诸如 create table 操作时，本质就是在写一个 Schema 。
NoSQL一般会被称为Schemaless数据库，侧面说明了NoSQL弱模式的特性。不过数据通常会有相当“连贯”的结构，为了建立索引，我们还是会显式的编写部分Schema描述这些连贯（consistent structure）的数据。
索引的数据结构
索引字面上很容易理解，例如 HashMap 和 Array，它们的 键值 (HashCode) 和 元素下标 (Index) 就是其索引。但数据库作为一个系统，在索引上的设计上就略微繁琐一些了，不过索引目的都是为了提高搜索效率，避免检索时枚举所有数据。
索引本质是一种数据结构，将数据按照某种规律排列就形成了索引，借用别人的话来说“索引就是排序的艺术”。
考虑在 1 亿条数据中，找到 id 为 4396 的数据这个场景。暴力遍历最差需要枚举 1 亿次才能找到。那 B+Tree 结构如何优化索引，考虑到有序树基本都是参考了二分法的思想，所以先从简单的二分法开始。
1 亿条数据一直对半分，最坏大概只需要 $log_2(1,0000,0000) \approx 26$ 次查询，可以看出仅仅一个平衡的二叉树（二分法）就可以指数级提升查找效率。
而数据库通常采用平衡多叉树结构，也就是 B+ Tree，B+ Tree 与二叉树最大的区别就是其多叉，即底数 N 可能大于 2，也就降低了阶数。但是每阶可能需要比较 N 次，这样算下来效率好像没有比二叉树好。不过结合现实世界考虑，通过索引磁盘 IO 读取数据的次数约等于树的阶数，多叉树远比二叉树的阶数少，减少了磁盘 IO 次数。
简单的理解一次 IO 然后 CPU 内存批量判断索引，比精确但频繁的 IO 读取索引挨个判断更快，CPU 是比磁盘快 IO 得多的。这也就是数据库系统中 B+ Tree 也就比二叉树的查询速度更快的原因了。
但显而易见的一棵多叉树，工作机制类似二分法，搜索效率很高~~（那么代价是什么）~~。但当我们增删数据时，需要分裂、合并叶子节点，那这棵树的结构会受到很大波动。因为树需要按照 B+ Tree 的规则（定义）平衡自己，称之为页的分裂与合并，一般是为了保持每个页的大小为 16K。所以常说建立索引后查询变快，但会导致增删改变慢。
表的存储结构
模式 (Schema) 与 索引 (Index) 终归和“物理数据”不太相关，物理数据是如何存储的？主要与表的存储结构相关。存储结构直接影响到数据的存储方式，间接影响到增删改查。关系型数据库的存储结构有两种：索引组织表 (Index Organzation Table) 与 堆表 （Heap Table）。
NoSql因为不使用关系表，在NoSql中或许可以类比的概念是数据模型。例如键值对模型、文档模型、图模型等。NoSql按照模型定义把数据存储成非结构化（unstructured）数据。
索引组织表
表的存储结构依附于索引，物理数据存储在一个索引的 B+ Tree 上，也可以说索引直接指向物理数据，找到了索引，就找到了数据，这个索引称之为聚集索引。物理数据只有一份，所以每个表也只能有一个聚集索引，一般为主键（唯一索引）。除聚集索引外的索引就是二级索引，也被称为辅助索引。
可以想象聚集索引是有序的，所以物理数据也是有序的，这意味着物理数据存储位置是随索引动态变化的，二级索引只能指向一个聚集索引（主键 ID）。当使用二级索引检索数据时，获取到聚集索引（主键 ID），再用主键 ID 去检索物理数据，这个过程叫作回表。
堆表
堆表则没有聚集索引，顾名思义堆表是一个 Heap，物理数据无序的堆在一起。数据与索引分开存储，通过索引只能获取到数据的物理地址（页号、偏移位置），再根据地址去直取物理数据。
表面上看这与索引组织表的二级索引机制大致相同，可以说堆表的索引全部都是二级索引，但堆表的二级索引不存在回表问题。与索引表的二级索引相比，存储的是数据的物理地址，所以少了回表步骤，不过与聚集索引相比，还是慢一点的。
另外显而易见由于堆表无序，所以存储速度比索引表快一些。
对于索引的优化
聚集索引
聚集索引影响一个表的物理数据存储顺序，数据存储到哪个位置取决于这个聚集索引，会影响存储速度。不过找到索引，也就找到了数据，提升查询速度。数据和索引聚集到一起了，两者间有很强的关系。然后我们把这个索引叫做 聚集索引，这种表结构的存储方式叫做 索引组织表。因为聚集索引影响表的物理数据存储顺序，所以一个表只能有一个聚集索引，通常是根据主键建立的 B+ Tree 索引。
根据聚集索引特性，我们可以优化的点：
- 范围查询时尽量命中聚集索引，可以降低回表次数。
- 更新数据时尽量不更改聚集索引本身。
- 尽量不要离散的增删数据。例如隔 10 条数据删一条这种。
MySQL 的 InnoDB 存储引擎就采用索引组织表。
二级索引 (辅助索引/非聚集索引)
二级索引的通常只存储了一个指向数据行存储位置的指针~~，当然还有索引列本身（作为键）~~。当我们通过二级索引列查询数据时，会先从辅助索引中找到记录的位置，这个位置上存放了数据行的指针。
- 在索引组织表结构下拿到的这个数据指针是主键（聚集索引）的值。 通过主键的值再去聚集索引树里查询数据，这个过程叫做回表
，SQL 语句耗时长的多数原因。 - 在堆表结构下拿到的数据指针则是数据存放的绝对位置（页码、偏移量）。 在堆表结构下，所有索引都可以看作是二级索引。
简单想象一个场景，现在我们想根据员工年龄查询数据，但我们目前只有一个用户 ID 列的聚集（主键）索引，数据库需要枚举所有数据再进行筛选。这时候我们就可以为年龄列建立一个二级索引。有了年龄列索引，数据库会先通过年龄列索引查询到符合条件的数据指针，再通过数据指针取到数据。
堆表与索引表的二级索引在读取数据时小有差异，不过宏观上看都是进行了两次 IO 读写，一次读取索引结构，一次读取数据页。这里可以把索引表的“数据页”看成聚集索引树，所以需要用主键指针重新走一遍聚集索引，查找数据。虽然都是两次 IO，不过这个过程肯定是不如堆表的绝对位置指针快的，不过也有优化方法。
覆盖索引
覆盖索引特性可以改善索引组织表的回表现象。简单来说，只要我们保证要查询的数据列都是索引列，这样找到二级索引就找到了所需要的数据，避免了再去聚集索引中查询数据。
例如我们要只想查询用户的 age 和 name，而恰好我们建立了 name 列和 age 列二级组合索引。
create index on user(age, name)
那我们此时应该避免写出类似 select * 语句。
-- 可能查询到不需要的列，会触发回表
select *
from user where age > 20 order by name
原因是查询 user 表没有索引的列会导致回表。例如 create_time 没有索引，数据库会再去聚集索引中取 create_time 数据，可我们的业务又不需要 create_time，白白浪费性能。
select name, age, create_time
from user where age > 20 order by name
只需要通过二级索引覆盖了要查询的所有数据，因为 (age,name) 组合索引本身就是 age, name 列的数据，通过这个索引筛选数据时，找到了索引，就找到了数据，所以避免了回表操作。
select name, age from user where age > 20 order by name;
-- or
select age from user where age > 20;
数据库锁
并发领域中常见术语：锁。
或许可以先看看我的《[[怎样安全的并发编程]]》文章 😳。
数据库根据颗粒度划分出行级锁、页级锁、表级锁。这些锁顾名思义就很容易理解了。根据行为来说的话又有共享锁和互斥锁。共享锁能够将数据设为只读，任一线程都可以读（共享数据），不过任一线程企图更新数据时都会被阻塞，直到共享锁释放。互斥锁则是为了保障写入数据的一致性，表现形式就是其它线程无法再对次数据添加任何锁。只有持有互斥锁的线程对该数据可读可写。
结合一个并发的先读后写的场景的业务场景。比如支付订单减少库存。A 用户和 b 用户同时了购买同一个商品，且同时支付成功。我们的业务逻辑是，首先为了保险，需要判断库存是否还有剩余，如果有剩余，就减少商品库存。
-- upodate 语句会自动请求互斥锁（锁定需要的数据）
update product set stock = stock - 1 where product_id = x and stock > 0;
这句 sql 利用了互斥锁，保证了数据的一致性。但如果放在日经问题“抢购/秒杀”上来看，同时上万个用户进行秒杀，数据一致性是没问题。但由于竞争互斥锁会出现阻塞，那响应速度可想而知，且数据库链接是昂贵的资源，开了连接却阻塞等待，~~（占着茅坑不拉屎），~~小鸡承受不住呀。
缓存一招鲜秒了，将 stock 这个数据缓存。当然，缓存那边怎么去实现，就牵扯到更多的缓存数据库设计了，一般是缓存好（预热/懒加载）数据，在缓存中原子性的更改缓存数据（库存）。然后在某个时间点进行一次简单地数据库更新写入，保证缓存与数据库的一致性。
-- 在某个时刻，写入最新缓存数据。节流数据库写入请求
update product set stock = #{stock_from_cache} where product_id = x
也没什么好说的，只要对并发编程理解足够深，把类似概念套用到数据库的锁、事务上也是一样的~~，只要打好基础，写啥都轻松~~。