二叉树和红黑树擦肩而过的MySql索引

MySql索引的四种数据结构:二叉树、红黑树、Hash表、B-Tree。为什么性感的二叉树和风骚的红黑树却与索引擦肩而过呢?

1、二叉树

索引二叉树结构图如下:

图1

(1)没有用索引时执行select*fromwheret.Col2=89,数据从磁盘一条一条拿去最终找到结果,效率低下。

(2)二叉树索引如上图右侧排列,右侧子节点大于父节点,左侧小于父节点,几点可能存储的是Key-value值,key为字段数据,value就是索引所在行数据在磁盘文件的指针位置。查询速度比无索引快。

缺点:在出现索引数据为1,2,3这种连续自增数据时体现为一个链表慢查询和无索引一致,索引擦肩而过。数据图如下:

图2

2.红黑树

二叉树的变种平衡树,具备自旋平衡同时改变颜色。完美的解决连续自增的问题,可是引入一个新问题。

图三

缺点:由于自选平衡解决了链表问题,可是当数据百万行之后,2的n次方就是数字总数,可是n就是树的高度,这个时候n的高度同样可观。随着数据的增加将不再适合做一个索引。

综上:两个经典的数据结构和Mysql前生的千百次回眸却换来与索引的擦肩而过,要想知道Mysql那个心仪的索引结构吗?请看下篇介绍。




转载请注明:http://www.aierlanlan.com/rzgz/2354.html

  • 上一篇文章:
  •   
  • 下一篇文章: