MySQL · TokuDB · TokuDB索引结构--Fractal Tree

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

MySQL · TokuDB · TokuDB索引结构--Fractal Tree

db匠 2016-05-23 15:56:21 浏览2964
展开阅读全文

背景介绍

TokuDB采用的是Fractal Tree作为索引的数据组织方式。它是一种面向磁盘I/O优化的数据结构,采用“分期偿还”策略减少在数据插入过程中从root节点到leaf节点的搜索过程。这种搜索过程可以简称为locate_position,就是寻找要插入key在Tree中位置的过程。

一般B+Tree的插入过程分为两个部分:

  1. Locate_position: 从root开始使用binary search方法递归地寻找应该插入到哪个子节点上,直到在leaf节点找到应该插入的位置然后返回;
  2. Insert_into_postion: 在locate_position返回的位置进行插入操作,如果当前leaf节点存储的key个数超过预定义的最大值可能会引起split操作,最坏的情况是引起从leaf节点到root节点的split。

Fract

网友评论

登录后评论
0/500
评论