On lzq ways

高级应用篇四

2019-06-23  本文已影响4人  zhengqiuliu

问题:在工作中,为了加速数据库中数据的查找速度,我们常用的处理思路是,对表中数据创建索引。那你是否思考过,数据库索引是如何实现的呢?底层使用的是什么数据结构和算法呢?

解题思路

1,定义清晰问题:功能性问题,限定需要解决问题的范围。假设我们要解决的问题,只包含如下两个常用的需求:

根据某个值查找数据:select * from user_table where id = 1234

根据区间值来查找某个数据:select * from user_table where id > 1234 and id < 2345

除了功能性需求之外,往往还需要涉及一些非功能性需求,比如安全,性能,用户体验等等。对于非功能性需求,我们着重考虑性能方面的需求。也就是执行效率和存储空间

2,尝试用学过的数据结构解决这个问题

需要支持快速查询,插入等操作的动态数据结构,我们已经学习过散列表,平衡二叉树,跳表。

散列表:查询性能很好,时间复杂度是O(1)。但是散列表不能支持按照区间快速查找数据。所以散列表不能满足我们的需求。

平衡二叉树:平衡二叉树查询性能很高,时间复杂度是O(logn)。并且对树进行中序遍历,可以得到一个从小到大右序的数据序列,但仍然不足以支持按照区间快速查找数据。

跳表:跳表是在链表之上加上多层索引构成的。它支持快速地插入,删除数据,对应的时间复杂度是O(logn)。并且跳表也支持按照区间快速地查找数据。这样看来,跳表是可以解决这个问题。实际上,数据索引所用到的数据结构跟跳表非常相似,叫做B+树

3,改造二叉查找树来解决这个问题

为了让二叉树支持按照区间来查找数据,我们可以对它进行这样的改造:树中的节点并不存储数据本身,而是只是作为索引。除此以外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。改造之后,如果我们要求某个区间的数据。我们只需要拿区间的起始值,在树中进行查找,当找到某个叶子节点之后,我们再顺着链表往后遍历,直到链表中的结点数据值大于区间的终止值为止。

但是,我们要为几千万,上亿的数据构造索引,如果将索引存储在内存中,尽管内存访问速度非常快,查询效率非常高,但是,占用的内存会非常多。

我们可以借助时间换空间的思路,把索引存储在硬盘中,而非内存中。硬盘的访问速度是毫秒级的,而内存的访问速度是纳秒级别的,取同样的数据,从磁盘中读取花费的时间是从内存中读取花费时间的上万倍。这样数据的查询效率就相应降低很多。

二叉查找树,经过改造之后,支持区间查找的功能就实现了。不过为了节省内存,如果把树存储在硬盘中,那么每个节点的读取,都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。

比起内存读取操作,磁盘IO操作操作非常耗时,我们优化的重点就是尽量减少磁盘IO操作,也就是尽量降低树的高度。那如何降低树的高度?

对于相同的数据构建m叉树索引,m叉树中m越大,那树的高度就越小,那m叉树中的m是不是越大越好呢?不管内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是4KB)来读取的,一次会读一页的数据。如果要读取的数据量超过一页的大小,就会触发多次IO操作。所以我们在选择m大小的时候,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只需要一次磁盘IO操作。

B+树总结

数据库索引实现,依赖的底层数据结构是B+树。它通过存储在磁盘的多叉树结构,做到了时间,空间的平衡,既保证了执行效率,又节省了内存。

特点:

1,每个节点中子节点的个数不能超过m, 也不能小于m/2;

2,根节点的子节点个数可以不超过m/2, 这是个例外

3,m叉树之存储索引,并不真正存储数据,这个有点类似跳表

4,通过链表将叶子节点串联在一起,这样可以方便按区间查找

5,一般情况下,根节点存储在内存中,其它节点存储在磁盘中。

B树和B+树的不同

B+树中节点不存储数据,只是索引,而B树中的节点存储数据

B树中的叶子节点并不需要链表来串联

B树只是一个每个节点的子节点个数不能小于m/2的m叉树。

上一篇下一篇

猜你喜欢

热点阅读