mysql 为啥用B+树结构
2019-02-21 11:58:00 小德 MySQL 访问次数 316


Q:B+树查询时间复杂度

log(N)


Q:Hash查询时间复杂度

O(1)


Q:为啥不用Hash  用B+树

  查询select  不止一条记录;

  内存大小限制;


有序序列 二叉排序树会退化成链表  ;


红黑树 保证树的平衡性;保证树的平衡性降低树的高度


B树是一种多路搜索树(拥有多余2个孩子节点的树);


多路有啥好处:

      降低树的高度;

      索引存在硬盘上,数据量大,内存有限,不能一次加载到内存,一次加载一个节点;

      如果涉及成无线多个孩子节点呢  会退化成有序数组;内存容量问题


B+树的作用  

查询范围; 如果没有叶子节点间的双向链表,会增加一次中序遍历,跨层访问;