MySQL · 引擎特性 · B+树并发控制机制的前世今生

  1. 云栖社区>
  2. 阿里云数据库ApsaraDB>
  3. 博客>
  4. 正文

MySQL · 引擎特性 · B+树并发控制机制的前世今生

db匠 2018-09-22 09:00:02 浏览797
展开阅读全文

前言

B+树是1970年Rudolf Bayer教授在《Organization and Maintenance of Large Ordered Indices》一文中提出的[1]。它采用多叉树结构,降低了索引结构的深度,避免传统二叉树结构中绝大部分的随机访问操作,从而有效减少了磁盘磁头的寻道次数,降低了外存访问延迟对性能的影响。它保证树节点中键值对的有序性,从而控制search/insert/delete/update操作的时间复杂度在O(log(n))的范围内。鉴于上述优势,B+树作为索引结构的构建模块,被广泛应用在大量数据库系统和存储系统中,其中就包括MySQL。

索引结构作为影响系统性能的关键因素之一,对数据库系统在高并发场景下的性能表现具有重大的影响。从1970年B+树提出至今,学术界有大量论文尝试优化B+树在多线程场景下

网友评论

登录后评论
0/500
评论
db匠
+ 关注
所属云栖号: 阿里云数据库ApsaraDB