数据库算法原理？

Question

一般数据库存放数据用的是什么结构和算法？有若干行有一个字段相同的情况数据如何存放？B树只能对一个字段进行索引
难道对每一个字段都建立一个索引树吗？

Answer 1

Q：一般数据库存放数据用的是什么结构和算法？
A：比较深入了。相关情况，跟小F姐的答案一致，可以参考 Inside 系列的存储引擎 这本书Q：有若干行有一个字段相同的情况数据如何存放？
A：就目前的情况，如果数据是null 可以使用稀疏列技术来进行存储优化。详情参考http://msdn.microsoft.com/zh-cn/library/cc280604.aspxQ：B树只能对一个字段进行索引
A：B树通过查找索引中的一个关键值来对数据进行快速访问。具体使用中就是聚集索引只能按照一个顺序将数据进行排列。但聚集索引可以选择多个列（字段）来进行建立。Q：难道对每一个字段都建立一个索引树吗？
A：实际使用中不会对每个字段建立索引树，毕竟索引时单独的结构，也需要消耗资源。建立索引，不一定会提高查询性能，有时候还会适得其反。这要看具体情况。Q：学生 与 选修课程 有多对应关系；实际存放的时候也是重复存放的吗
A：多对一的关系，是依靠约束来进行控制的，这属于数据有效性的范畴。实际存放过程中会重复存放。当然仅仅是对应的IDQ：那么查找数据时用的什么算法 遍历全表
A：查询的时候，如果没有索引，就会表扫描，如果有索引，数据库引擎会根据测算的查询成本来选择，需要使用表扫描，还是索引扫描，或者是索引查找等

Answer 2

SQL Server由两个主要引擎组成：关系引擎(relational engine)和存储引擎(storage engine)。关系引擎有时候被称为查询处理器，因为关系引擎的主要功能是进行查询的优化和执行。关系引擎包含三个主要部分，命令分析器(command parser)、查询优化器(query optimizer)和查询执行器(query executor)。 命令分析器用于检查查询命令的语法和生成查询树，查询优化器大概是任何数据库系统中最重要的一部分，查询执行器负责查询命令的执行。存储引擎负责管理与数据有关的所有I/O操作，包括访问方法(access methods)的代码和缓冲区管理器(buffer manager)。其中，访问方法负责处理行、索引、页、分配和行版本的I/O请求；缓冲区管理器负责缓冲池的管理，缓冲池是SQL Server内存的主要消耗者。存储引擎还包含了一个事务管理器，负责数据的锁定以实现ACID属性中的隔离性，并负责管理事务日志。