Listening to the Words

MySQL语言勉強中之毕加索的树

MySQL语言勉強中之毕加索的树

索引是作用是什么?

简单的说,汉语大辞典如果没有索引,你该如何查询’歪’字, 只能一页一页的翻。
因此为了提高查询效率,才有了索引,mysql是索引作用和字典索引一模一样。

mysql索引特点

索引存储在文件系统中,这也和不同的索引有关,例如memory引擎存储在内存里

索引数据结构

  • hash
  • 二叉树
  • 二叉查找
  • 二叉平衡树
  • 红黑树
  • B树
  • B+树

为什么选择了B+树

hash

hash的缺点:hash碰撞,根据算法可能造成占用内存和分布不均衡,等值查询时很快,范围查询效率低下,memory引擎使用hash,索引存储内存里,因此很快

二叉树们

  • 二叉树
  • 二叉查找
  • 二叉平衡树
  • 红黑树

二叉树不符合mysql索引选取的缺点是:数据量大会导致数据节点特别多,导致I/O消耗大,查询效率低

B树和B+树

B树:

《MySQL语言勉強中之毕加索的树》

B+树:

《MySQL语言勉強中之毕加索的树》

B树的特点是节点多,存储量大,分布均匀,非常便于扫描查询,因此mysql选择了这种数据结构.
但是有一个问题:如果每个节点又放索引和数据(data),会导致数据存储总量下降,怎么理解呢?

 1 张老爷有四个孩子,一个男孩子四个女孩子,这个男性家谱会有多大的树形结构取决于儿子能生几个男孩子
 2 张老爷有四个孩子,四个男孩子,那么此时这个家谱会有多大? 
 显然会比第二种更庞大一些

因此B树还有进步的空间,这时就有了B+树,所有的数据都放在叶子节点上。

一层二层节点上存放的都是索引ID和指针,通过指针一级查找下一级。

InnoDB+B+tree 索引存储结构

《MySQL语言勉強中之毕加索的树》

MyISAM+B+tree 索引存储结构

《MySQL语言勉強中之毕加索的树》

点赞