【数据库】数据库元素的层次，树形结构的下的多粒度加锁，以及幻象的正确处理

数据库元素的层次

专栏内容：

手写数据库toadb
本专栏主要介绍如何从零开发，开发的步骤，以及开发过程中的涉及的原理，遇到的问题等，让大家能跟上并且可以一起开发，让每个需要的人成为参与者。
本专栏会定期更新，对应的代码也会定期更新，每个阶段的代码会打上tag，方便阶段学习。

开源贡献：

toadb开源库

个人主页：我的主页
管理社区：开源数据库
座右铭：天行健，君子以自强不息；地势坤，君子以厚德载物.

文章目录

数据库元素的层次
前言
概述
多粒度的锁
警示锁
- 警示协议规则
- 警示锁相容性矩阵
幻象与插入的正确处理
总结
结尾

前言

随着信息技术的飞速发展，数据已经渗透到各个领域，成为现代社会最重要的资产之一。在这个大数据时代，数据库理论在数据管理、存储和处理中发挥着至关重要的作用。然而，很多读者可能对数据库理论感到困惑，不知道如何选择合适的数据库，如何设计有效的数据库结构，以及如何处理和管理大量的数据。因此，本专栏旨在为读者提供一套全面、深入的数据库理论指南，帮助他们更好地理解和应用数据库技术。

数据库理论是研究如何有效地管理、存储和检索数据的学科。在现代信息化社会中，数据量呈指数级增长，如何高效地处理和管理这些数据成为一个重要的问题。同时，随着云计算、物联网、大数据等新兴技术的不断发展，数据库理论的重要性日益凸显。

因此，本专栏的分享希望可以提高大家对数据库理论的认识和理解，对于感兴趣的朋友带来帮助。

概述

前面我们分享了不同的封锁模式，本文主要介绍数据库元素，也就是加锁的对象，它可能是以树结构出现的，此时就会出现两个问题：

遇到第一类树结构，是可封锁的层次结构。本文将介绍如何才能既允许大的元素，如表上的锁，又允许包含其中的较小元素上的锁，如块或元组。
并发控制系统中另一类重要的层次是本身的结组形式就是一棵树，如B-树索引。如果将它看成一个数据库元素进行加锁，那么封锁模式下的性能就会非常低，我们需要一种新的方法；

如何解决和优化这两类问题，将在下文中详细介绍。

多粒度的锁

数据库元素，在前面介绍时并没有特别的说明，因为在不同数据库的实现中各不相同，有整个表，也有数据块，还有表元组。有些应用受益于小的数据库元素，而有的在大的数据库元素下表现更好。

假如给每一个元组提供一个锁，那么对于银行帐户业务，不管有什么样的帐户集合都可以同时更新，但不值得为这样细粒度的锁付出特别大的代价。

作为对照，考虑文档的一个数据库，这些文档可能不时被编辑，但大数据事务将检索整个文档。如果将整个文档作为一个数据库元素，对于同时编辑或查看文档的动作，将不能进行。

这样看来需要使用大粒度锁，又能使用小粒度锁，可以使一些应用更新效率。但是，为了计算表上的聚集而获得了一个表的共享锁，而同时在单个元组上又有排它锁，这可能会导致非可串行化的行为。

下面我们来看一些延伸出来的锁模式。

警示锁

解决管理不同粒度的这一问题的方法，又延伸出来一种新的锁，警示锁，也叫意向锁。如同它的名字，它只是警示的作用，在数据库元素形成嵌套或层次结构时很用作用。

在这里插入图片描述

如上图，可以看表表，块，元组三个层级；

表是最大的可封锁的元素；
每张表是一个或多个块组成；每个块上存储了表的元组；
每个块包含了一个或多个元组；

在数据库元素层次上管理锁的规则由警示协议构成，它既包括普通锁，又包括警示锁。
警示锁的表示，在普通锁S和X的封锁模式前加前缀I表示，如IS表示获取子元素上的一个共享锁意向。

警示协议规则

要在任何元素上加S或X锁时，我们必须从层次结构的根开始；
如果处于将要封锁的元素位置时，则不需要进一步查找，请求该元素上的S或X锁。
如果希望锁的元素位于层次结构的中下时，首先在这一结点上加一个警示锁；也就是说，想要获得其子元素上的共享锁时，先请求该结点上的IS锁，如果想要获得其子节点的排它锁时，先请求该结点上的IX锁，接下来重复这一步，直到到达所需要的结点。