说说B+ Tree

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

先看下B+ Tree数据结构的特点(From Wikipedia).

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次数也就越少.

说说B+ Tree

在MySQL中, 不同的存储引擎, 使用B+ Tree数据结构, 形成了各自存储数据的方式. 对于InnoDB存储引擎来说, 是Clustered index(聚簇索引)的存储方式, (在Oracle中叫索引组织表, 即index-organized table). 在MyISAM存储引擎中, 就是堆表的存储方式. 下图可以较直观的反应两者数据的组织方式.

说说B+ Tree

左上方图聚簇索引中,

a. 非叶子结点存储的是, <Primary key, Pointer>.

b. 叶子结点存储的是, 一行行记录.

左下方图二级索引中,

a. 非叶子结点储存的是, <Key, Pointer>.

b. 叶子结点存储的是, <Key, Primary key>.

右图索引结构中,

a. 非叶子结点存储的是, <Key，Pointer>.

b. 叶子结点存储的是, <Pointer>, 其指向记录.

下面看看B+ Tree数据结构的efficient retrieval和high fanout特点, 在InnoDB存储引擎中是如何体现的. 以左上图为例, 假设使用Bigint数据类型(8Bytes)作为主键, 一条记录大小为400Bytes, Page大小为16K, 那么索引树高度为1, 2, 3层时, 存储的记录有多少(注, Pointer大小为6Bytes).

说说B+ Tree

现在普通的SAS盘, 一秒钟也可以完成200次I/O, 从千万量级的数据中, 检索一条记录, 只要3次I/O, 即0.015秒就行了, 可见效率之高, 又加之目前一般使用的SSD盘, 最少也要再快50倍.

最后看看两种数据存储方式的优缺点.

1. 观察第二幅图片, 在InnoDB存储引擎中使用二级索引检索数据时, 由于其叶子结点存储的是<Key, Primary key>, 在获取到Primary key时, 还要去查看聚簇索引, 即回表操作, 才能获取到记录. 而在MyISAM存储引擎中, 主键索引和二级索引具有同等地位(只不过主键索引值非空), 检索数据时, 无需回表. 也许从该点来说MyISAM存储引擎更适合查询.

2. 对于DML操作, 一条记录从400Bytes变更到600, 若不能原地更新的话, 在MyISAM存储引擎中, 索引叶子结点存储的是指向记录的指针, 相比InnoDB存储引擎来说, 其变动会更大些. 也许从该点来说InnoDB存储引擎更适合变更. 当然了, 两者为了预防非原地更新产生的影响, 都会在Page中预留空洞.

若感兴趣可关注订阅号”数据库最佳实践”(DBBestPractice).

说说B+ Tree