求教C/C++ 中二叉树等的实际应用问题。

芮淼一线 发布于 2015/01/02 19:49
阅读 709
收藏 1

我们都知道利用二叉树,红黑树等来实现数据的查找等操作是比较好的算法。

        如果要查找的数据已经在内存中时我知道怎么利用二叉树来实现查找(比如说可以把这棵二叉树抽象理解为一棵实树然后就一步一步去找就行了),但是我如果要从很大的一堆数据中查找,而且这堆数据并没有直接放在内存中,比如是在数据库中。

        在数据库中可以直接使用select语句查询。现如果说在很大很大的一张表中查找数据,如果用select语句它是从表头一项一项游走到表尾(不知道我理解错没用)这样岂不是很慢,或者说数据库已经对大数据的查找等操作进行过优化处理(形如二叉树算法等)。

        如果数据库本身对表操作只能从表头到表尾,那么我要实现快速的查找等操作是不是就可以利用二叉树算法了,如果可以这么做,那我又该如何实现。

        请大家帮忙回到一下,如果有时间的朋友能不能给我一个示范代码(如在SqlServer中利用二叉树算法实现查找,其它SQL也行),谢谢。

加载中
0
中山野鬼
中山野鬼

无论你查什么,最粗的可分结构化的和非结构化的。结构化的,简单理解,你待查找的对象,都有相同的性质,只不过存储上也是具备结构特性的。更抽象的说,就是一个集合中,你寻找特定要求的元素。

再细分,对一个集合中元素的查找,如果该集合是有序的。则可以通过元素与元素之间已经存在的固有关系(序关系),选择性的寻找集合中的某些子集合。

上面这个就是二叉树等快速查找的理论基础。如果一个集合是无序的,用这些没有任何意义。哈。

superchris
superchris
大学里多些像你这样的老师就好了
G_Young
G_Young
受教了,野鬼前辈总能从数据结构的本质出发直击要害。我若想像您一样对数据结构和算法进行深入理解,野鬼前辈有没有什么好的建议? 或者有什么好的书籍推荐? 亦或者有什么好的方法途径?
0
k
kchr

简略来说,如果没有索引,那确实是全表遍历,不断读取硬盘,非常缓慢的。

索引实际上是对表预先作了一次排序,而且由于频繁使用很可能已经缓存在内存中的,所以 select 此时只是在内存中做一个折半查找(根据索引的性质可能更优化),然后直接获得所要数据在磁盘中的位置。读取搞定!

0
k
kchr

另外说一句,一个 SQL 数据库,本质上也就是写在硬盘上的一些数据。

虽然电气性能天差地远,从抽象的编程接口来看,硬盘和内存可以看作是没有区别的。

linux 下,你可以用 mmap 内存映射 API 把一个文件虚拟成一块内存,也可以越过文件系统直接操作 /dev/sda 裸设备。


0
k
kchr
范例代码,BerkelyDB 或者 SQLite 都可以。
芮淼一线
芮淼一线
????
0
k
kchr

引用来自“kchr”的评论

范例代码,BerkelyDB 或者 SQLite 都可以。
有啥好 ??? 的。BerkelyDB 就可以配置成采用 B 树作底层结构。

反过来,也有内存虚拟成硬盘的产品啊...我见过接在 PCI-E 接口的。

闪存同样虚拟硬盘做成 SSD,天天用 ...

索引,预留空记录,考虑硬盘内外磁道的线速度差异...这都是优化。但最基本的数据结构

是通用的。

没道理内存可以用,硬盘不可以用...

返回顶部
顶部