Read and write models and organize notes

Read the model

1、 Primary key read

The most common reading model , Say primary key , In fact, it also includes other index keys , Or union primary key .

Common implementation ：hash, The time complexity can be close to O(1);B Trees or varieties ： Time complexity is close to O(log(n)).

About B Trees and varieties ：

B Trees （B- Trees ）： In essence, it is an upgraded version of binary search tree , Become balanced N Fork search tree , This N The range of is adjusted according to the block size read by the disk at a time , This complexity log n The base number of is from 2 Into a larger number , Reduced the height of the tree . in addition to , There are some additional optimizations , For example, for the performance of insertion and deletion , Usually prepare some reserved space , As long as the space is found in the current block or adjacent blocks , It avoids all the backward offset operations of records with huge overhead .

B The steps of the tree ：

1. A tree m Step B Trees have at most m Kezi tree ;
2. The root node has at least two subtrees ;
3. Each non root branch node has at least ceil(m/2) Kezi tree ;
4. Leaf nodes are all on the same layer ;
5. Yes x Children's non leaf nodes happen to have x-1 Keywords in ascending order .

The picture is from This page .

B+ Trees ： and B Trees are compared to , Changes include ：

1. All keyword information is placed in the leaf node ;
2. All leaf nodes are strung into one linked list In order to search ;
3. Store duplicate search keys .

For specific differences, please refer to 《Difference between B Tree and B+ Tree》,（ The following is from ）.

B* Trees in B+ Further improvements have been made on the basis of tree ：

1. Non leaf nodes add pointers to sibling nodes （ Used when the node is full , You can put data into brother nodes , Reduce node creation ）;
2. Non leaf nodes must be at least 2/3 Full of （ The number of keywords must be at least the maximum 2/3）.

2、 Specify page query

Specifying pages means having the concept of paging , For example DynamoDB Query interface design , You can pass in a LastEvaluatedKey Such an object , Locate the starting position of this page by reading the primary key . however , If you want to randomly specify the page number of the query , The complexity of this situation varies greatly in different implementations , Some can directly calculate the position of the page , Others need to start from the first page and go down page by page .

Common implementation ： Specify starting position , In the case of conditional query, the data subset is returned .

3、 Range queries

First , Data can be sorted according to a certain attribute , Then there is the concept of range query . For example, queries where the user's age is within a certain range .

Common implementation ：B Trees and their varieties （ In this case B+ Tree ratio B The superiority of trees is reflected ,B+ Trees can scan leaf nodes directly linked list that will do ）.

4、 Full data scanning

This access model usually means low speed and high overhead , Generally used as asynchronous tasks , For example, report system , Do regular data statistics during low access periods . Generally, non key queries are also full data scanning in nature .

Example ： Database full table scan ,Hadoop Data set processing task on .

5、 Full text search

Common implementation ： Inverted index .

6、 Prefix / The suffix match

Prefix matching ：Trie Trees ; The suffix match ： Suffix tree . See 《Trie Comparison between tree and other data structures 》.

7、 Conditions of the query

Common implementation ： Full table scan ;R Trees ;Space-filling Curve.

Write model

1、 Asynchronous update

Back first , Do not pay attention to the transactional nature of updates , The update operation is completed in the background , This method has the fastest result return speed .

2、 queue / deque

This situation is applicable to the case that the throughput is relatively large and very unstable , With the buffer function of queue ; There is also a problem of writing order , With the help of the order of priority queue .

3、 Batch write

In many cases, it is asynchronous data processing , Such as data backfilling 、 Batch data export, etc .

4、 Update according to the query results

Is to merge the two-step process of query and update , Make it atomic . such as Java Medium compareAndSet operation , For example, database update Statement follow where Clauses and so on .

5、 Insert or update

upsert, Like hash map Medium put, No matter whether the record exists before , Existence covers , Insert if it doesn't exist .

6、 Update to multiple replication

Almost all production storage systems will consider replication, For the problem of data reliability , Redundancy of multiple data at the software level is the only way .

The articles are all original without special indication , It shall not be used for any commercial purpose without permission , Please keep the integrity of reprint and indicate the source link 《 Four fire's nagging 》