说说B+Tree-创新互联
先看下B+ Tree数据结构的特点(From Wikipedia).
创新互联致力于互联网网站建设与网站营销,提供做网站、成都网站设计、网站开发、seo优化、网站排名、互联网营销、小程序定制开发、公众号商城、等建站开发,创新互联网站建设策划专家,为不同类型的客户提供良好的互联网应用定制解决方案,帮助客户在新的全球化互联网环境中保持优势。1. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context - in particular, filesystems.
2. B+ trees have very high fanout(number of pointers to child nodes in a node, typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
对于第2点, 看看下图, 每个结点都含有指向下一层的指针, 指针越多, 意味着树的高度就越矮, 即在块设备(常见的就是磁盘)中检索数据, 需要的I/O次数也就越少.
在MySQL中, 不同的存储引擎, 使用B+ Tree数据结构, 形成了各自存储数据的方式. 对于InnoDB存储引擎来说, 是Clustered index(聚簇索引)的存储方式, (在Oracle中叫索引组织表, 即index-organized table). 在MyISAM存储引擎中, 就是堆表的存储方式. 下图可以较直观的反应两者数据的组织方式.
左上方图聚簇索引中,
a. 非叶子结点存储的是,
b. 叶子结点存储的是, 一行行记录.
左下方图二级索引中,
a. 非叶子结点储存的是,
b. 叶子结点存储的是,
右图索引结构中,
a. 非叶子结点存储的是,
b. 叶子结点存储的是,
下面看看B+ Tree数据结构的efficient retrieval和high fanout特点, 在InnoDB存储引擎中是如何体现的. 以左上图为例, 假设使用Bigint数据类型(8Bytes)作为主键, 一条记录大小为400Bytes, Page大小为16K, 那么索引树高度为1, 2, 3层时, 存储的记录有多少(注, Pointer大小为6Bytes).
现在普通的SAS盘, 一秒钟也可以完成200次I/O, 从千万量级的数据中, 检索一条记录, 只要3次I/O, 即0.015秒就行了, 可见效率之高, 又加之目前一般使用的SSD盘, 最少也要再快50倍.
最后看看两种数据存储方式的优缺点.
1. 观察第二幅图片, 在InnoDB存储引擎中使用二级索引检索数据时, 由于其叶子结点存储的是
2. 对于DML操作, 一条记录从400Bytes变更到600, 若不能原地更新的话, 在MyISAM存储引擎中, 索引叶子结点存储的是指向记录的指针, 相比InnoDB存储引擎来说, 其变动会更大些. 也许从该点来说InnoDB存储引擎更适合变更. 当然了, 两者为了预防非原地更新产生的影响, 都会在Page中预留空洞.
若感兴趣可关注订阅号”数据库最佳实践”(DBBestPractice).
另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站名称:说说B+Tree-创新互联
分享地址:http://myzitong.com/article/djsejc.html