⑴ 数据库原理和数据结构有什么区别
数据结构是电脑里数据的组织方式,或者说存储方式,是一种什么结构来存取数据,例如典内型的堆栈结构容stack,队列结构queue，链表结构list等，堆栈是后进先出last
in
first
out
（lifo），队列结构是first
in
first
out(fifo)，链表是任意位置插入新数据之类的，简单来说就是找一种方式方便你存取你的数据。
数据库是一个数据集合，顾名思义，库就是一个存储地方嘛，即存放大量数据的地方，而往数据库里放数据或者访问数据库里的数据的方式就是数据结构的内容了。
数据库相当于一个容器，数据结构相当于你往容器里放东西的方式和取东西的方式，如果没有数据结构，那么容器里的东西（数据）就会杂乱无章，以后取出来也麻烦。两个理念，一句两句说不清楚，重要的是看书
⑵ 跪求数据结构快速排序法原理
看看这个吧，里面讲的十分详细了已经。
http://hi..com/apollo_hj/blog/item/d39a372bb3fea93e5243c110.html
---
以上，希望对你内有所帮助。容
⑶ 什么是数据结构简述数据结构主要包含内容. 设置操作系统的主要目的是什么操作系统有哪些基本功能
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
操作系统（Operating System，简称OS）是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能：进程与处理机管理、作业管理、存储管理、设备管理、文件管理。以现代观点而言，标准个人电脑OS应提供以下功能：进程管理（Processing management） ；记忆空间管理（Memory management） ；文件系统（File system） ；网络通讯；安全机制（Security） ；使用者界面 ；驱动程序。目前微机上常见的操作系统有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。
⑷ Redis的五种数据结构及其底层实现原理
redis的字符串类型是由一种叫做简单动态字符串(SDS)的数据类型来实现
SDC和C语言字符串的区别：
1：SDS保存了字符串的长度，而C语言不保存，盯棚凯只能遍历找到第一个 的结束符才能确定字符串的长度
2：修改SDS，会检查空间是否足够，不足会先扩展空间，防止缓冲区溢出，C字符串不会检查
3：SDS的预分配空间机制，可以减少为字符串重新分配空间的次数
备注：重新分配空间方式，小于1M的数据 翻倍+1，例如：13K+13K+1，如果大于1M，每次多分配1M，例如：10M+1M+1,如果字符串变短，并不会立即缩短，而是采用惰性空间释放，有专门的API可以释放多余空间
hash结构里其实是一个字典，有许多的键值对
redis的哈希表是一个dictht结构体：
哈希表节点的结构体如下：
hash算法：
当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
hash冲突解决方式：链表法，后入的放到最前面
rehash：
键值数据量变动时，时为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或和仿者收缩。
如果是扩充，新数组的空间大小为 大于2*used的2的n次方，比如：used=5,则去大于10的第一个2的n次方，为16
如果是缩小，新数组的空间大小为第一个不大于used的2的n次方，比如：used=5,则新大小为4
redis的list列表是使用双向链表来实现的
···
typedef struct listNode {
struct listNode * pre; //前置节点
struct listNode * next; //后置节点
void * value; //节点的值
}
typedef struct list {
listNode *head; //表头节点
listNode tail; //表尾节点
unsigned long len; //链表所包含的节点数量
void ( p) (void ptr); //节点值赋值函数 这里有问题
void ( free) (void ptr); //节点值释放函数
int ( match) (void *ptr, void *key) //节点值对比函数
}
···
1：有序集合的底层实现之一是跳表， 除此之外跳表它在 Redis 中没有其他应用。
2：整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。
3：数据少是，使用ziplist(压缩列表)，占用连续内存，每项元素都是(数据+score)的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大数据(long long),就多用一些字节存储，而对于小的数据(short)，就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。
无序集合可以用整数集合(intset)或者凯唤字典实现
Redis的5.0版本中，放出一个新的数据结构Stream。其实也是一个队列，没一个不同的key对应的是不同的队列，没个队列的元素，也就是消息，都有一个msgid，并且需要保证msgid是严格递增的。在Stream当中，消息是默认持久化的，即便是Redis重启，也能够读取到信息。
Stream的多播，与其它队列系统相似，对不同的消费者，也有消费者Group这样的概念，不同的消费组，可以消费通一个消息，对于不同的消费组，都维护一个Idx下标，表示这一个消费群组费到了哪里，每次进行消费，都会更新一下这个下标，往后面一位进行偏移。
跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而大道快速访问节点的目的，具有以下性质：
1：有很多层结构组成
2：每一层都是一个有序的链表，排列顺序为由高到低，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点
3：最底层的链表包含了所有的元素
4：如果一个元素出现在某一层的链表中，那么在该层之下的链表也全部都会出现
5：链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的通一个链表节点
多个跳跃表节点构成一个跳跃表
1：搜索，从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也及时和当前层的下一层的节点下一个节点
2：插入，首先确定插入的层数，有一种方法是抛一个硬币，如果是正面就累加，直到遇到反面为止，最后记录正面的次数作为插入的层数，当确定插入的层数K后，则需要将新元素插入从底层到K层
3：删除，在各个层中找到包含指定值得节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。
整数集合是Redis用于保存整数值集合的抽象数据类型，它可以保存int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。
整数集合的每个元素都是contents数组的一个数据项，他们按照从小到大的顺序排列，并且不包含任何重复项。
length属性记录了contents数组的大小。
需要注意的是虽然contents数组声明为int8_t类型，但是实际上contents数组并不保存任何int8_t类型的值，其真正类型由encoding来决定。
压缩列表(ziplist)是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或一个整数值。
压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩的，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。
压缩列表的每个节点构成如下：