发明名称 |
一种基于AVL树的数据写入方法及装置 |
摘要 |
本发明公开了一种基于AVL树的数据写入方法及装置,采用读写锁对数据写入进行并发控制,包括:接收数据的写入请求;根据写入节点值的大小以及AVL树的特性确定搜索路径;判断所述搜索路径中各节点是否处于锁状态;其中,锁状态为在当前并发的写操作中第一节点为发生局部调整子树的根节点时,将所述第一节点设置为锁住的状态;若所述搜索路径中没有节点处于锁状态,则进行写操作;若所述搜索路径中有节点处于锁状态,则将写操作阻塞至锁住的节点上,直至所述锁住的节点的锁状态取消。本发明所提供的基于AVL树的数据写入方法及装置,对AVL树中局部未冲突的写操作允许并行处理,从而提高数据写入的性能。 |
申请公布号 |
CN105389360A |
申请公布日期 |
2016.03.09 |
申请号 |
CN201510745287.5 |
申请日期 |
2015.11.05 |
申请人 |
浪潮(北京)电子信息产业有限公司 |
发明人 |
杨敏 |
分类号 |
G06F17/30(2006.01)I |
主分类号 |
G06F17/30(2006.01)I |
代理机构 |
北京集佳知识产权代理有限公司 11227 |
代理人 |
罗满 |
主权项 |
一种基于AVL树的数据写入方法,其特征在于,采用读写锁对数据写入进行并发控制,包括:接收数据的写入请求;根据写入节点值的大小以及AVL树的特性确定搜索路径;判断所述搜索路径中各节点是否处于锁状态;其中,锁状态为在当前并发的写操作中第一节点为发生局部调整子树的根节点时,将所述第一节点设置为锁住的状态;若所述搜索路径中没有节点处于锁状态,则进行写操作;若所述搜索路径中有节点处于锁状态,则将写操作阻塞至锁住的节点上,直至所述锁住的节点的锁状态取消。 |
地址 |
100085 北京市海淀区上地信息路2号2-1号C栋1层 |