Q:为什么Mysql选择使用B+树作为索引结构?
A:核心原因是使用了B+树之后,磁盘IO最少,如果把数据存储在磁盘中,磁盘的读取(随机读取)比内存慢10万倍,
索引的设计是为了减少磁盘IO,所以选择B+树
Q:B+树为什么可以做到这样?
A: (1)树矮,B+树是多叉树,一层可以存取几百上千条数据,三层可以存取两千多万条数据,所以,使用B+树作为索引结构,一般情况下,查三次就差不多就能查到数据,但是,对于红黑树(红黑树是二叉树)来说,相同的数据需要几十层来存取,读取时候,IO直接爆掉
(2)非叶子节点只存储key和指针,不存储数据,相同的页面可以存储更多的索引,内存缓存更多的索引,搜索命中率高,磁盘访问次数降低
(3) B+树采用双向链表,查找数据确定起点后,直接从起点出发,向后找数据,不用再次返回根节点在出发,顺序查找比随机查找的效率要高
扩展知识:
Q:为什么不使用哈希作为索引?
A:虽然说哈希结构在查找指定数据的时间复杂度为O(1),比B+树的O(log n)要小一点,但是哈希结构有以下缺点,
第一:不支持范围查询,比如查找 50>age>25的程序员,B+树直接沿着链表走一遍就行了,而哈希需要一个一个找
第二:不支持排序,按照从大到小排列,B+树直接把结果拿出来就行了,而哈希表还需要先排序
另外还有一个小知识,InnoDB并没有完全放弃哈希结构,在频繁访问一个数据索引的时候,数据库会自动创建一个哈希结构,方便更快访问该数据,这是自动生成的,不需要人为操纵(不需要手动创建)
Q:为什么不使用红黑树,和AVL树:
A:首先 红黑树和AVL树都是二叉树,当数据量大的情况下,需要好多层存取key,但是B+树是多叉树,三层可以存两千多万条数据,对于红黑树和AVL树来说需要几十层,使用B+树最多查三次就可以获得结果,,但是使用红黑树和AVL树需要好多次磁盘访问
Q:B+树和B树的区别?(或者为什么MongoDB早期使用B树,后来又换成B+树了呢?)
A: 首先他两都是多叉平衡树,最核心的区别就是存储数据
1:B树所有节点都存储完整数据,而B+树叶子节点存储完整数据,非叶子节点只存储key和指针,这会让B+树能存储更多的索引,存储更多的索引,命中率就高,访问磁盘次数就少
2:B+树是双向链表,而且是顺序查询,比B树的随机查询效率要高(B+树用链表串起来,在范围查询时候直接顺序扫描,B树做范围查询需要不断回到上层节点在往下找,io次数多)
3:由于B树所有节点都存储数据,所以可以查询到非叶子节点,就查询到了数据,查询到数据的时间不稳定,B+树所有数据存储在叶子节点上,所以每次查询都是查到叶子节点,时间稳定
Q:为什么InnoDB要求主键尽量短?
A:核心:主键越短,非叶子节点存储的key越多,存储的索引越多,命中率高,磁盘访问次数少
