数据库存储结构有哪些

‘壹’ 数据结构：八种常见数据结构介绍

八种常见数据结构介绍

一. 数组（Array）

数组是有序元素的序列，在内存中的分配是连续的。数组会为存储的元素都分配一个下标（索引），此下标是一个自增连续的，访问数组中的元素通过下标进行访问，数组下标从0开始。

• 优点：访问数据简单，由于数据是存储在连续空间内，所以每个数据的内存地址都可以通过数据下标算出，因此可以直接访问目标数据（随机访问）。
• 缺点：添加和删除数据比较耗时间，因为需要移动其他数据以腾出空间或填补空缺。
• 使用场景：频繁查询，对存储空间要求不大，很少增加和删除的情况。

二. 链表（Linked List）

链表是由一系列节点（也可称元素）组成，数据元素的逻辑顺序是通过链表的指针地址实现。每个节点包含两个部分，一个用于存储元素的内存地址（数据域），另一个则指向下一个相邻节点地址的指针（指针域）。根据链表的指向不同可分为单向链表、双向链表、循环链表等。

• 优点：数据添加和删除方便，只需改变指针的指向即可。
• 缺点：访问比较耗费时间，因为数据都是分散存储的，需要从头节点开始逐一访问。
• 适用场景：数据量较小，需要频繁增加、删除操作的场景。

三. 栈（Stack）

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是先进后出，从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）。

• 特点：后进先出（LIFO），即最后插入的元素最先被移除。
• 适用场景：需要逆序处理数据的场景，如函数调用栈、浏览器历史记录等。

四. 队列（Queue）

队列与栈一样，也是一种线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。队列的特点是先进先出，从一端放入元素的操作称为入队，取出元素为出队。

• 特点：先进先出（FIFO），即先插入的元素先被移除。
• 适用场景：需要按顺序处理数据的场景，如任务调度、消息队列等。

五. 散列表（Hash）

散列表也叫哈希表，是根据键和值（key和value）直接进行访问的数据结构。通过key和value来映射到集合中的一个位置，从而快速找到集合中的对应元素。它利用数组支持按照下标访问的特性，是数组的一种扩展。

• 数据存储：使用哈希函数将key转换为数组索引的下标，然后将value存储在该下标对应的数组位置。
• 冲突解决：当两个key的哈希值相同（冲突）时，可以使用链表在已有数据的后面继续存储新的数据（链地址法），或者使用开放地址法等方法解决。
• 特点：查找速度快，但空间利用率可能不高（需要预留足够的数组空间以减少冲突）。

六. 树（Tree）

树是一种数据结构，由n（n>=1）个有限节点组成一个具有层次关系的集合。每个节点有0个或多个子节点，没有父节点的节点称为根节点，每一个非根节点有且只有一个父节点，除了根节点外，每个子节点可以分为多个不相交的子树。

• 常见类型：二叉树（每个节点最多有两个子节点）、平衡二叉树、红黑树、B+树等。
• 特点：添加、删除元素都很快，并且在查找方面也有很多的算法优化。
• 应用：数据库索引结构（如B+树）、HashMap底层源码（如红黑树）等。

七. 堆（Heap）

堆可以看做是一颗用数组实现的二叉树，没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。堆中某个节点的值总是不大于或不小于其父节点的值。

• 类型：最大堆（根节点最大）、最小堆（根节点最小）。
• 特点：完全二叉树结构，满足堆属性。添加、删除元素的时间复杂度为O(log n)。
• 应用：优先队列、堆排序等。

八. 图（Graph）

图是一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

• 类型：有向图（边具有方向）、无向图（边无方向）。
• 特点：可以表示复杂的关系网络，如社交网络、交通网络等。
• 应用：路径搜索（如Dijkstra算法、Floyd-Warshall算法）、最短路径问题、网络流问题等。

以下是部分数据结构的图示：

这些数据结构各有优缺点，适用于不同的应用场景。在实际编程中，需要根据具体需求选择合适的数据结构来优化算法和提高程序性能。

‘贰’ 数据库有哪几种

数据库模型：对象模型、层次模型（轻量级数据访问协议）、网状模型（大型数据储存）、关系模型、面向对象模型、半结构化模型、平面模型（表格模型，一般在形式上是一个二维数组。如表格模型数据Excel)。
数据库的架构可以大致区分为三个概括层次：内层、概念层和外层。
Operational-Relational Database
典型应用场景: ERP， CRM， 信用卡交易处理， 小型电子商务
数据存储方式: 表格
主流厂商: Oracle Database， Microsoft SQL Server， IBM DB2， SAP Hana， Amazon Aurora， Azure SQL Database， Enterprise DB (PostgreSQL)， MySQL， MemSQL
优势：成熟的生态环境，事务保证/数据一致性
劣势：严格的数据模型定义，数据库扩展限制，与非结构化的融合使用较难。
Analytical-Relational Database
典型应用场景: 数据仓库，商务智能，数据科学
数据存储方式: 表格
主流厂商: Oracle Exadata， Oracle Hyperion， Teradata， IBM Netezza， IBM dashDB， Amazon Redshift， Microsoft SQL Data Warehouse， Google BigQuery
优势: 信息和计算的一致性
劣势: 需要针对数据库专业的IT人员维护，数据响应数据通常在分钟级
Operational-Nonrelational Database
典型应用场景: Web， mobile， and IoT applications， social networking， user recommendations， shopping carts
数据存储方式: 有很多存储结构 (document， graph， column， key-value， time series)
主流厂商: MongoDB， Amazon DynamoDB， Amazon，DocumentDB， Azure CosmosDB， DataStax， Neo4j， Couchbase， MarkLogic， Redis
优势: 易用性，灵活性(不需要预定义的模式)，水平伸缩(以适应大量数据量)，一般低成本(开源)
劣势: 缺乏事务保证
Analytical -Nonrelational Database
典型应用场景: 索引数以百万计的数据点，预测性分析，欺诈检测
数据存储方式: Hadoop不需要固有的数据结构; 数据可以跨多个服务器存储
主流厂商: Cloudera， Hortonworks， MapR， MarkLogic， Snowflake， DataBricks， ElasticSearch
优势: 适合批量处理， 并行处理文件; 主要是开源的，投入较低
劣势: 缓慢的响应时间; 不适合快速查找或快速更新