摘要
Abstract
Red-black tree is a widely used balanced search tree data structure.traditional red-black tree relies on locks for synchronization,which can lead to contention and limit its performance in concurrent scenarios.In this paper,we propose a lock-free red-black tree algorithm that overcomes the limitations of traditional red-black trees.This paper introduces a lock-free synchronization technique to design lock-free red-black tree data structures using fine-grained atomic operations and optimistic concurrency control.The proposed algorithm implements lock-free basic operations such as lookup,insertion and deletion and optimizes write operations to ensure concurrency control for read operations.To evaluate the performance of lock-free red-black tree,experiments are conducted under different hardware and software configurations using different datasets and performance metrics.The experimental results show that the lock-free red-black tree outperforms the traditional lock-based red-black tree in both single-threaded and multi-threaded scenarios.关键词
红黑树/无锁同步机制/无锁红黑树/自平衡二叉查找树/数据结构Key words
red-black tree/lock-free synchronization mechanism/lock-free red-black tree/self-balancing binary lookup tree/data structure分类
信息技术与安全科学
