Search Algorithms and Data Structures

About Me

RDBMS is …

https://www.geeksforgeeks.org/database-file-indexing-b-tree-introduction/

Composite Index

CREATE INDEX class_pos_index ON users (class, position);

eComm Facets

Inverted Index

Lucene, Solr and Elasticsearch

http://www.supercoloring.com/coloring-pages/romulus-and-remus-with-the-she-wolf.

The First Indices

Общественное достояние, https://commons.wikimedia.org/w/index.php?curid=433142

https://rbscp.lib.rochester.edu/489

Term Dictionary

rubens
rub*
[rome TO rustic]
*uber
*man*

By Claudio Rocchini - Own work, CC BY

Offsets to Postings List File

10: 8, 9, 10, 14, 18, 23,

Postings Codecs

delta 8, 9, 10, 14, 18, 23 => 1,1,1,4,4,5
vint 5

Query Execution

Stored Field Retrieval

{"name": "first doc", "count": 43} {"name": "another doc", "count":5}

Indexing

Index Document

curl -X PUT "localhost:9200/twitter/tweet/1" -H 'Content-Type: application/json' -d'
{
"user" :

Mapping

curl -X PUT "localhost:9200/my_index" -H 'Content-Type: application/json' -d'{
"mappings": {
"properties":

Analysis

curl -X PUT "localhost:9200/my_index" -H 'Content-Type: application/json' -d'
{ "settings": { "analysis":

In-memory Buffer

{
"user" : "kimchy",
"message" : "trying out
Elasticsearch"
}

user

message

Segments

1,2,2,3

1

2,2,1

_refresh

Elasticsearch: The De€nitive Guide
Copyright © 2015 Elasticsearch. All rights reserved.

_refresh vs _flush

Elasticsearch: The De€nitive Guide
Copyright © 2015 Elasticsearch. All

Indexing Performance

_bulk
Threads
ETL is hard

Searching

Result Page

{
"timed_out": false,
"took": 62,
"_shards":{
"total" : 10,
"successful"

Result Page Cropping

10: 8, 9, 10, 14, 18, 23, 24, 26,

https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations-bucket-terms-aggregation.html

Real Life Usage

Elastic Logstash Kibana (ELK) Stack

https://www.elastic.co/guide/en/logstash/current/deploying-and-scaling.html

Scaling

https://www.digitalocean.com/community/tutorials/understanding-database-sharding

Summary

Why search?
Inverted Index
Indexing
Searching
Scaling
ELK

200 threads

https://blog.newrelic.com/engineering/expected-distributions-website-response-times/

2,2,1

Index Hierarchy

2,2,1

2,2,1

Segment - inverted index

Lucene Index - chain

Shard

Elasticsearch Index

Index pattern:

An Index is …

an derived data structure

Term Frequency

red

red bar

red red red bar red