think-about-data-structure

文章目录

1. 1. 内存保存
2. 2. 磁盘保存
3. 3. 混合内存和硬盘保存包括数据的生命周期来实现

为什么有数据结构的问题就是数据本来是无序和杂乱的
怎么在保存的时候方便后续更加方便查询和分析
如果是像记事本和word这种的确是可以使用单考虑到大量的数据就要考虑效率和成本

最后就发现了很多方法

• 内存保存
• 基于机械硬盘保存附以数据结构
• 混合内存和硬盘保存包括数据的生命周期来实现

内存保存

redis,Cassandra,Neo4j 等将数据保存在内存中实现快速存储,同时还提供数据的持久化,和过期时间,同时包括其他的有效特性

磁盘保存

1. 二分查找: 将文件数据有序保存，使用二分查找来完成特定key的查找。
2. 哈希：用哈希将数据分割为不同的bucket
3. B+树：使用B+树 或者 ISAM 等方法，可以减少外部文件的读取
4. 外部文件： 将数据保存为日志，并创建一个hash或者查找树映射相应的文件。

基于硬盘的保存就要优先考虑磁盘原理,磁盘的探测器读取磁道的数据,所以数据是顺序读写的,且会预读取数据到内存,目前很多开发的分布式服务都基于此设计为(LSM Log Structured-Merge Tree) 包括kafka, hbase 等尽量避免顺序读写

b+数这类设计目标提高数据的查询的效率,在数据保存的时候将数据建议归类以树状的结构排列,同时在包括叶子节点和根节点来实现快速找对数据节点

通常数据库还有一个方式 WAL(writte ahaead log) 即写数据之前会先累积数据后在保存在

现在常见的数据保存结构有哪些

树状结构 b数,b+树,b-树

线性 lsm结构 数据保存读写会累积不是覆盖这种

数据库索引常见,b-tree,hash,gist,gin,sp-gist,brin

方便查询

方便读写

B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型，这主要是因为B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。
一般来说， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node ，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，所以我们大家都称之为 B-Tree 索引当然，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个Leaf Node (叶子节点)上面出了存放索引键的相关信息之外，还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。
B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互链接。
在B+树上的常规检索，从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速左右移动，效率非常高。
因此，B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下，xfs文件系统比ext3/ext4效率高很多的原因之一就是，它的文件及目录索引结构全部采用B+树索引，而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构，因此在高I/O压力下，其IOPS能力不如xfs。

所以使用

混合内存和硬盘保存包括数据的生命周期来实现

代表程序为 elasticsearch

数据过来会被建立索引保存在内存中后面会被保存在磁盘,数据的生命周期为hot warm cold delete

阶段 / action	优先级设置	取消跟随	滚动索引	分片分配	只读	强制段合并	收缩索引	冻结索引	删除
hot	√	√	√	×	×	×	×	×	×
warm	√	√	×	√	√	√	√	×	×
cold	√	√	×	√	×	×	×	√	×
delete	×	×	×	×	×	×	×	×	√