【数据库】树形数据组织架构下的封锁并发控制,B树索引并发访问控制,树协议原理及案例分析

本文主要是介绍【数据库】树形数据组织架构下的封锁并发控制,B树索引并发访问控制,树协议原理及案例分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数据库并发访问树协议

专栏内容

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

开源贡献

  • toadb开源库

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

文章目录

  • 数据库并发访问树协议
  • 前言
  • 概述
  • 树结构的封锁不同点
  • 树协议的规则
    • 举例
  • 树协议原理分析
  • 总结
  • 结尾

前言

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

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

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

概述

有一类数据库元素,它的组织结构是树的形式,树中的各元素之间没有包含关系,如B-树索引数据的组织形式,对于此类数据的访问必须从树进行查找访问,这与之前介绍的数据库元素的层次结构,在加锁方式上不一样。

本文将重点介绍树形结构组织的数据的访问规则,封锁原理,以及一些优化的谈讨。

树结构的封锁不同点

  • 访问需要加锁; 在访问树形数据时,假如是B-树索引,为了保持读写操作的可串行化,需要进行封锁访问,锁模式如之前提到的读锁,写锁,更新锁;

  • 加锁粒度为节点;树的每个节点也是一个数据块,加锁粒度也是节点,更小到元组会带来更多不利,更大的粒度到整棵树,那几乎没有并发性了;

  • 加锁方式与2PL有区别;树的访问都是从根开始,然后一层层遍历,找到对应节点位置;那么加锁也从根开始,按之前介绍的两阶段锁规则,在使用前不能释放锁,那就意味着根节点没有并发性,这不利用索引的使用效率。如果确定不修改树节点,那么就可以提前释放根节点的锁,这就有悖2PL;

基于以上不同,对于树形组织的数据,专门使用树协议加锁方式,而不是2PL方式加锁,在确定当前节点还有空间时,就不会修改根节点,此时就可以提前释放根节点的锁,同样适用于中间节点,当然串行化的保证依赖于都从根往下顺次查找这一顺序。

树协议的规则

树协议由以下规则构成,假定访问树结构使用一种锁,用L(X)来表示加锁X节点;

  • 访问树结构时,第一个锁可以加在树中的任意节点;

  • 只有持有父节点的锁时,才能对其后续节点加锁;

  • 事务可以在任何时候解锁;

  • 不能对已解锁的节点重新加锁,即使此时持有父节点的锁也不行;

举例

在这里插入图片描述

并发三个事务,T1 从节点A开始移动,经过B,C,D;事务T2从B开始,目标是E节点;事务T3从E开始,移动到F和G;其中加锁是L(X),解锁是U(X)表示。

T1T2T3
L1(A);R1(A);
L1(B);R1(B);
L1©;R1©;
W1(A);U1(A);
L1(D);R1(D);
W1(B);U1(B);
L2(B);R2(B);
L3(E);R3(E);
W1(D);U1(D);
W1©;U1©;
L2(E) 被拒绝
L3(F);R3(F);
W3(F);U3(F);
L3(G);R3(G);
W3(E);U3(E);
L2(E);R2(E);
W3(G);U3(G);
W2(B);U2(B);
W2(E);U2(E);

这个例子中,事务T1,T2,T3是按照树协议进行并发调度,其中T2在加锁E节点时,与T3节点发生冲突,导致它被延迟,在T3释放E节点锁之后又得以继续执行。

树协议原理分析

树协议在调度中,锁涉及的事务中的必然包含一个串行动作序列,因为它们都是从上到下的访问顺序,这个可以用优先图来证明,如果优先图中没有环的存在,说明它等价一个可串行化的调度。

通过上面协议规则和树的访问顺序,在一棵树中,两个事务并发时,可以得出以下判断;

  • 假如有几个节点,两个事务都需要加锁,那么这几个节点上的加锁顺序是一样的;

因为两个事务访问的公共元素有两个或两个以上时,每个事务加锁的节点可以组成一个子树,两个子树的交也是一棵子树,访问时也是从最高节点开始,依次向下加锁,所有公共元素的加锁顺序是一致。

总结

对于树形组织的并发访问的控制,不能使用两阶段锁的模式,为了提升并发访问效率,通过树协议,可以提前释放当前节点路径上的锁。

结尾

非常感谢大家的支持,在浏览的同时别忘了留下您宝贵的评论,如果觉得值得鼓励,请点赞,收藏,我会更加努力!

作者邮箱:study@senllang.onaliyun.com
如有错误或者疏漏欢迎指出,互相学习。

这篇关于【数据库】树形数据组织架构下的封锁并发控制,B树索引并发访问控制,树协议原理及案例分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/467500

相关文章

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

mybatis的整体架构

mybatis的整体架构分为三层: 1.基础支持层 该层包括:数据源模块、事务管理模块、缓存模块、Binding模块、反射模块、类型转换模块、日志模块、资源加载模块、解析器模块 2.核心处理层 该层包括:配置解析、参数映射、SQL解析、SQL执行、结果集映射、插件 3.接口层 该层包括:SqlSession 基础支持层 该层保护mybatis的基础模块,它们为核心处理层提供了良好的支撑。

百度/小米/滴滴/京东,中台架构比较

小米中台建设实践 01 小米的三大中台建设:业务+数据+技术 业务中台--从业务说起 在中台建设中,需要规范化的服务接口、一致整合化的数据、容器化的技术组件以及弹性的基础设施。并结合业务情况,判定是否真的需要中台。 小米参考了业界优秀的案例包括移动中台、数据中台、业务中台、技术中台等,再结合其业务发展历程及业务现状,整理了中台架构的核心方法论,一是企业如何共享服务,二是如何为业务提供便利。

Hadoop企业开发案例调优场景

需求 (1)需求:从1G数据中,统计每个单词出现次数。服务器3台,每台配置4G内存,4核CPU,4线程。 (2)需求分析: 1G / 128m = 8个MapTask;1个ReduceTask;1个mrAppMaster 平均每个节点运行10个 / 3台 ≈ 3个任务(4    3    3) HDFS参数调优 (1)修改:hadoop-env.sh export HDFS_NAMENOD

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

MySQL数据库宕机,启动不起来,教你一招搞定!

作者介绍:老苏,10余年DBA工作运维经验,擅长Oracle、MySQL、PG、Mongodb数据库运维(如安装迁移,性能优化、故障应急处理等)公众号:老苏畅谈运维欢迎关注本人公众号,更多精彩与您分享。 MySQL数据库宕机,数据页损坏问题,启动不起来,该如何排查和解决,本文将为你说明具体的排查过程。 查看MySQL error日志 查看 MySQL error日志,排查哪个表(表空间

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和