0. 索引就是树吗

Last updated 4 years ago

Was this helpful?

设计原则

因为我们不能用顺序查找, 因此用树这种结构来降低时间复杂度. 与一般的树放在内存里不同, 数据库里用的树是放在磁盘里的.

B+树每个节点不存数据, B+树只在叶节点上存储已经排序过的数据, 各个叶节点之间通过指针串联在一起, 造成了链表一样效果. 也正是因为非叶节点不存储数据, 在非叶节点间跳转并不需要磁盘IO

按照B树的结构, 每访问一个节点则意味着一次随机IO, 一个比较极端的例子是如果我们执行一次这样的查询: select * from users where id > 4

但如果是在B+树中这种问题就很好办了, 因为是顺序读写都很快, 我们也不用回到上一层, 因为页节点有指针能直接前往下一个叶节点.

B树的每个节点都存有实际数据, 也就对应着磁盘里的一页, 这意味着我们每去访问一个节点中的数据, 都要去把磁盘里的数据读出来, 相应的就是一次磁盘IO.

刚刚数落了B树一通, 什么又是向下又是向上, 感觉性能一定很差, 现在又说Mongo默认使用B树, 一下子, 不知道该吹谁黑谁了... 其实出现这种原因主要是出于需求上的差异:

如果是这样说一下清楚很多了, 因为非叶节点也能存储数据, 因此我们可能都不用走到叶节点就可以查到数据, 更加节省了时间

最后说一说哈希, 我们用B树也不是代表我们就不支持按照"id>4"的方式去查询, 只是稍微慢一点, 但是如果哈希搞"id>4"就是遍历, 这点是不可接受的

我们曾经在B/B+树里面说过Mongo认为他的用户用 [where id=x] 这样的显示指定会更多, 因此选择了将数据存在非叶节点上以减少IO次数(而降低了范围查找的权重). 但如果真的你决定只有 [where id=x] 这种情况, 那么其实有更适合你的数据结构

哈希表, 这种表在等值查询里可以说是造快, 在Memcached这种存储, 只有kv存储的情况下非常的快, 缺点也是如果你想搞范围查找, 就很恐怖了