B+树作为数据库索引布局的上风对比

MySQL作为数据库，它的功能就是做数据存储和数据查找；使用B+树作为索引布局是为了实现高效的查找、插入和删除操纵。
B+树的查找、插入、删除的复杂度都为 O(log n)，它是一个多叉树的布局，能分身各种操纵的服从的数据布局。如果使用均衡二叉树大概红黑树，树的高度就会涨的很快，查询的次数就会变多了，倒霉于查找，磁盘的I/O次数就会变多。
范围查找很快，B+树的叶子节点是使用双向链表链接起来的，找到要查找的范围，序次读取就可以了
扩展

我们可以用作查找、插入和删除的数据布局有：数组、链表、哈希表、树、堆、跳表、字典树…
数组

查找：有序数组使用二分查找复杂度为 O(log n)，如果是无序数组须要遍历，查找复杂度为 O(n)
插入和删除的复杂度，在最坏情况下都是 O(n)
链表

查找复杂度为 O(n)，由于每次都须要重新开始遍历
插入如果直接都在头部插入复杂度为 O(1)，须要有序的话复杂度为 O(n)；删除复杂度为 O(n)
哈希表

查找、插入和删除都是抱负情况下为 O(1)，如果辩说较多会退化到 O(n)
为什么不消？

  

• 基于哈希函数举行索引的，不能做范围查找，部分查询  
  
• 辩说较多各个操纵会退化到 O(n)
  

二叉树（AVL树、红黑树、2-3树）

查找、插入和删除都是 O(log n)
为什么不消？

  

• 磁盘的存储服从不高，每个节点包罗的数据太少，查找时会存在大量的寻址开销  
  
• 由于这个只有二叉，在数据量很大的时间，树的高度会很大的影响各个操纵的服从
  

B树

查找、插入和删除都是 O(log n)
为什么不消？

  

•