精华内容
下载资源
问答
  • 2020-03-24 01:29:47

    逻辑关系映射到物理存储的映射方式有4种:顺序、链式、索引、哈希,相应地就产生了四种存储结构:顺序存储结构、链式存储结构、索引存储结构、哈希存储结构

    顺序存储

    • 特点:存储空间的地址连续,数据元素依次存放;利用物理相邻表示(存储)逻辑关系。
    • 优点:存储密度大;可以随机访问,在O(1)内查询、修改元素。
    • 缺点:表示关系能力弱;维护关系困难(逻辑关系发生变化,物理上难同步),在O(n)内插入和删除数据;存储空间必须一次获得(适用性差)。

    链式存储

    • 特点: 占用空间任意,元素任意存放;在存放元素的同时,还存放与其有关系的元素的地址(指针)。
    • 优点:空间任意;显式地存储关系;表示关系的能力强;在O(1)内插入、删除元素(只需改变结点的指针),便于动态管理内存。
    • 缺点:空间开销大,占用空间较多,存储密度小;必须通过指针来访问元素,在O(n)内查找、修改元素。

    索引存储

    • 特点:存储空间是多段连续空间,在存储结点信息的同时,还建立附加的索引表,索引表由若干索引项组成。
    • 优点:顺序和链式结合;数据检索速度快,保证数据的唯一性。
    • 缺点:创建索引和维护索引需要时间,而且索引也会占用一定的物理空间;对数据增删查改的同时也要对索引进行维护。

    哈希存储

    • 特点:又称散列存储,数据元素的存储位置和关键码(在数据结构中,指的是数据元素中能起标识作用的数据项)之间有着确定对应关系,其基本思想是由结点的关键码值决定结点的存储地址,除了用于查找外还可以用于存储,存储空间是连续空间。(有的HASH函数为取模函数)
    • 优点:利用数据的某一特征访问和存储,访问速度快,在O(1)内遍历元素。
    • 缺点:好的HASH很难;有时会产生冲突。
    更多相关内容
  • 1.顺序存储 平均时间复杂度为O(n) 空间复杂度为O(0)查找,删除,增加的时间复杂度为O(0),修改的时间复杂度为O(1)优点:存储空间紧凑,容易进行查找缺点:插入删除需要移动大量元素。需要分配大量空间2.索引存储...

    1.顺序存储  

    平均时间复杂度为O(n)   空间复杂度为O(0)

    查找,删除,增加的时间复杂度为O(0),修改的时间复杂度为O(1)

    优点:存储空间紧凑,容易进行查找

    缺点:插入删除需要移动大量元素。需要分配大量空间

    2.索引存储

    元素个数为M 索引数为N   查找的时间复杂度为O(M/N)  插入删除增加的时间复杂度为O(1)

    本质为一个指针数组,数组的每一个元素可以是动态数组,链表,树或者图

    #pragma once
    template<class T>
    class myvector
    {
    public:
    	myvector();
    	~myvector();
    	void push_back(T t);
    	T* find(T t);
    	void show();
    	void change(T* pos, T t);
    	void del(T t);
    	void insert(int pos,T t);
    	T operator [](int i);
    public:
    	T* p;
    	int n;
    	int reallen;
    };
    #include "myvector.h"
    #include <iostream>
    
    using namespace std;
    /*
    myvector();
    ~myvector();
    void push_back(T t);
    T *find(T t);
    void show();
    void change(T *pos, T t);
    void del(T t);
    void insert(T *pos,T t);
    */
    
    template<class T>
    myvector<T>::myvector()
    {
    	p = nullptr;
    	n = reallen = 0;
    }
    
    template<class T>
    myvector<T>::~myvector()
    {
    	if (p != nullptr)
    	{
    		delete[]p;
    		n = reallen = 0;
    	}
    
    }
    //从尾部插入数据
    template<class T>
    void myvector<T>::push_back(T t)
    {
    	if (p == nullptr)
    	{
    		p = new T;
    		*p = t;
    		n = reallen = 1;
    	}
    	else
    	{
    		T* ptemp = new T[n + 1];
    		for (int i = 0;i < n;i++)
    		{
    			ptemp[i] = p[i];
    		}
    		delete[]p;
    
    		p = ptemp;
    
    		p[n] = t;
    
    		reallen += 1;
    		n += 1;
           
    	}
    }
    //查找数据元素返回位置
    template<class T>
    T* myvector<T>::find(T t)
    {
    	for (int i = 0;i < reallen;i++)
    	{
    		if (p[i] == t)
    		{
    			return p + i;
    		}
    	}
    	return nullptr;
    }
    //打印数据元素
    template<class T>
    void myvector<T>::show()
    {
    	if (p == nullptr)
    	{
    		return;
    	}
    	for (int i = 0;i < reallen;i++)
    	{
    		cout << "p[" << i<<"]="<<p[i] << endl;
    	}
    
    }
    //改变数据元素
    template<class T>
    void myvector<T>::change(T *pos, T t)
    {
    		if (pos == nullptr)
    		{
    			 return;
    		}
    		else
    		{
    			*pos = t;
    		}
    }
    //删除数据
    template<class T>
    void myvector<T>::del(T t)
    {
    	int pos = -1;
    	for (int i = 0;i < reallen;i++)
    	{
    		if (p[i] == t)
    		{
    			pos = i;
    			break;
    		}
    	}
    	if (pos != -1)
    	{
    		if (pos == reallen - 1)
    		{
    			reallen -= 1;
    		}
    		else
    		{
    			for (int i = pos;i < reallen - 1;i++)
    			{
    				p[i] = p[i + 1];
    			}
    		}
    	}
    }
    //插入数据
    template<class T>
    void myvector<T>::insert(int pos, T t)
    {
    	if (pos>0 && pos<= n)
    	{
    		
    	//重新分配内存并拷贝
    			
    	  T *ptemp = new T[n + 1];//重新分配内存
     
          for (int i = 0; i < n; i++)
    	  {
    		  *(ptemp + i) = *(p + i);//拷贝  
    	  }
    	  
    	  delete []p;
    	  p = ptemp;
    	  reallen += 1;
    	  n += 1;
    		
    	}
    	for(int i = reallen-2;i>=pos;i--)	
    	  {
    		p[i+1] = p[i];//往前移动
    		}
    		p[pos] = t;	
    }
    //重载操作符
    template<class T>
    T myvector<T>::operator[](int i)
    {
    	if (i < 0 || i >= reallen)
    	{
    		return NULL;
    	}
    	return  p[i];
    }
    #include "myvector.h"
    #include "myvector.cpp"
    #include<iostream>
    //顺序存储
    using namespace std;
    void main1()
    {
    	myvector<int> myv;
    
    	myv.push_back(12);
    	myv.push_back(15);
    	myv.push_back(13);
    	myv.push_back(10);
    
    	myv.insert(2,9);
    
    	cout<<myv.find(12)<<endl;
    
    	myv.change(myv.find(13),8);
    	myv.show();
    
    
    	cin.get();
    
    }
    //索引存储
    void main()
    {
    	myvector<int> mv1;
    	mv1.push_back(1);
    	mv1.push_back(2);
    	mv1.push_back(3);
    	mv1.push_back(4);
    	mv1.push_back(5);
    	myvector<int> mv2;
    	mv2.push_back(11);
    	mv2.push_back(12);
    	mv2.push_back(13);
    	mv2.push_back(14);
    	mv2.push_back(15);
    
    	myvector<myvector<int>*> mvv;
    	//存储的是vector类型的地址,通过地址查找相应内存块获得数据
    	mvv.push_back(&mv1);
    	mvv.push_back(&mv2);
    	mvv[0]->show();
    	mvv[1]->show();
    
    
    	cin.get();
    
    
    	
    
    }

    3.链式存储:

    明确元素位置后,增加,插入,删除,修改的时间复杂度都为O(1), 查找的时间复杂度为O(n)

    优点:增加,删除

    缺点:查找复杂

    #pragma once
    
    template <class T>
    class node
    {
    public:
    	node();
    	~node();
    public:
    	T data;
    	node* pnext;
    };
    #pragma once
    #include "node.h"
    template<class T>
    class list
    {
    public:
    	list();
    	~list();
    	void add(T t);
    	void show();
    	node<T>* find(T t);
    	void change(node<T> *pos,T newt);//修改
    	void insert(T oldt,T newt);
    	bool deletel(T t);
    	void deletesame();//删除相同元素
    	bool deleteall();
    	bool clear();
    	void rev();
    	void sort();
    	int getnum();
    	void merge(list<T> &ll);
    
    	 
    
    
    public:
    	node<T> *phead;
    };
    #include "node.h"
    #include<iostream>
    using namespace std;
    template<class T>
    node<T>::node()
    {
    }
    template<class T>
    node<T>::~node()
    {
    }
    #include "list.h"
    #include "node.h"
    #include "node.cpp"
    #include<iostream>
    using namespace std;
    template<class T>
    list<T>::list()
    {
    	this->phead = nullptr;
    	cout << "list creat" << endl;
    }
    
    template<class T>
    list<T>::~list()
    {
    	cout << "list ruin" << endl;
    }
    //增加结点
    template<class T>
    void list<T>::add(T t)
    {
    	node<T> *p = new node<T>;//分配结点
    	p->data = t;
    	p->pnext = nullptr;
    	if (phead == nullptr)
    	{
        	this->phead = p;
    	}
    	else
    	{
    		node<T> *pt=phead;
    		while(pt->pnext!=nullptr)
    		{
    			pt= pt->pnext;
    		}
    		pt->pnext= p;
    	}
    
    }
    //打印结点
    template<class T>
    void list<T>::show()
    {
    	node<T> *ptemp = phead;
    	if (phead == nullptr)
    	{
    		cout << "null"<<endl;
    		return;
    	}
    	while (ptemp!= nullptr)
    	{
    		cout << ptemp->data << "->";
    
    		ptemp = ptemp->pnext;
    	}
    	cout << endl;
    }
    //查找结点
    template<class T>
    node<T>* list<T>::find(T t)
    {
    	node<T> *p = phead;
    	while (p != nullptr)
    	{
    		if (p->data == t)
    		{
    			return p;
    		}
    		p = p->pnext;
    	}
    	return nullptr;
    
    }
    //改变结点的值
    template<class T>
    void list<T>::change(node<T> *pos, T newt)
    {
    	if (pos == nullptr)
    	{
    		return;
    	}
    	pos->data = newt;
    }
    //结点的插入运算,在指定结点前面插入结点,
    template<class T>
    void list<T>::insert(T oldt, T newt)
    {
    	node<T> *p = this->find(oldt);//查找指定结点的位置
    	if (p != nullptr)
    	{
    		node<T> *p1, *p2;
    		p1 = phead;
    		p2 = p1->pnext;
    		while (p2!=p)
    		{
    			p1= p2;
    			p2 = p1->pnext;
    		}
    		//插入新的节点
    		node<T> *pnew = new node<T>;
    		pnew->data = newt;
    		p1->pnext = pnew;
    		pnew->pnext = p2;
    	}
    
    
    }
    //删除结点
    template<class T>
    bool list<T>::deletel(T t)
    {
    	cout << "delete "<< t<<endl;
    	node<T> *p = this->find(t);
    	//判断所删除的数据是否存在,链表是否为空
    	if (phead == nullptr || p== nullptr)
    	{
    		return false;
    	}
    	else
    	{
    		if (p == phead)//判断所删除的结点是否为头结点
    		{
    			phead = p->pnext;
    			delete p;
    			return true;
    		}
    		//找到所删除的结点以及指向它的结点,令指向他的结点指向该结点的下一个结点,并删除该结点
    		node<T> *p1=phead,*p2=p1->pnext;
    		while(p2!=p)
    		{
    			p1 = p2;
    			p2 = p1->pnext;
    		}
    		p1->pnext = p2->pnext;
    		delete p2;
    		return true;
    	}
    	return false;
    }
    //删除相同结点
    template<class T>
    void list<T>::deletesame()//删除相同元素
    {
    	cout << "deletesame" << endl;
    	//将链表的值从头结点开始依次与后面结点的值比较,用指针pf记录被比较结点的前一个结点,如果比较值相等则删除后面的结点,让前一个结点指向被删除结点的后一个结点。
    		for (node<T> *pt1 = phead;pt1 != nullptr;pt1 = pt1->pnext)
    		{
    			node<T> *pf = pt1;//记录前一个结点
    			for (node<T> *pt2 = pf->pnext;pt2 != nullptr;pt2 = pf->pnext)
    			{
    
    				if (pt1->data==pt2->data)
    				{
    					//删除相等结点,让前一个结点指向被删除结点的后一个结点
    					pf->pnext = pt2->pnext;
    					delete pt2;
    				}
    				else
    				{
    					pf = pt2;//如果值不相等则向后移动
    				}
    			}
    		}
    		/*
    		node<T> *p1,*p2;
    		p1=phead->pnext;
    		p2=phead;
    		while(p1!=nullptr)
    		{
    		  if(p1->data==p2->data)
    		  {
    		    p2->pnext=p1->pnext;
    			delete p1;
    			p1=p2->pnext;
    		  }
    		  else
    		  {
    		    p2=p1;
    			p1=p1->pnext;
    		  }
    		}
    		
    		
    		
    		*/
    }
    //删除所有结点
    template<class T>
    bool list<T>::deleteall()
    {
    	cout << "deleteall" << endl;
    	node<T> *ptemp=nullptr;
    	while (phead->pnext!=nullptr)
    	{
    		ptemp = phead->pnext;
    		delete phead;
    		phead = ptemp;
    		this->show();
    	}
    	delete phead;
    	phead=nullptr;
    	return true;
    }
    //清空链表
    template<class T>
    bool list<T>::clear()
    {
    	node<T> *p1, *p2;
    	p1 = phead->pnext;
    	while (p1!=nullptr)
    	{
    		p2 = p1->pnext;
    		delete p1;
    		p1=p2
    	}
    	delete phead;
    	phead = nullptr;
    	return true;
    }
    //链表反转
    /*
         a  ->  b  ->  c  ->  d  ->  e    
    	 p1 <-  p2     p3
    	        p1 <-  p2     p3
    			       p1 <-  p2     p3
    				          p1 <-  p2     p3
    						         p1     p2     p3
    nullptr<-phead				   phead  nullptr
    */
    template<class T>
    void list<T>::rev()
    {
    	cout << "rev " << endl;
    	if (phead == nullptr || phead->pnext == nullptr)
    	{
    		return;
    	}
    	else
    	{
    		node<T> *p1, *p2,*p3;
    		p1 = phead;
    		p2 = p1->pnext;
    		while (p2!=nullptr)
    		{
    			p3 = p2->pnext;
    			p2->pnext = p1;
    
    			p1 = p2;
    			p2 = p3;
    		}
    		phead->pnext = nullptr;
    		phead= p1;
    
    	}
    }
    //对链表进行排序
    template<class T>
    void list<T>::sort()
    {
    	cout << "sort" << endl;
    	if (phead == nullptr || phead->pnext == nullptr)
    	{
    		return;
    	}
    	else
    	{
    		for (node<T> *pt1 = phead;pt1 != nullptr;pt1 = pt1->pnext)
    		{
    			
    			for (node<T> *pt2 = pt1->pnext;pt2 != nullptr;pt2 = pt2->pnext)
    			{
    				if (pt1->data > pt2->data)
    				{
    					pt1->data = pt1->data + pt2->data;
    					pt2->data= pt1->data - pt2->data;
    					pt1->data = pt1->data - pt2->data;
    					continue;
    				}
    			}
    		}
    	}
    }
    //获取链表结点个数
    template<class T>
    int list<T>::getnum()
    {
    	int num = 0;
    	node<T> *p = phead;
    	while (p != nullptr)
    	{
    		num++;
    		p = p->pnext;
    	}
    	cout << "count=" << num<<endl;
    	return num;
    }
    //链表的连接
    template<class T>
    void list<T>::merge(list<T> &ll)
    {
    	cout << "merge连接" << endl;
    	node<T> *p=phead;
    	while (p->pnext!=nullptr)//找到最后一个结点
    	{
    		p = p->pnext;
    	}
    	p->pnext = ll.phead;
    	
    }
    #include<iostream>
    #include<string>
    #include "list.h"
    #include "list.cpp"//模板类必须将实体包含,或者生成库
    using namespace std;
    //链表的实现
    void main1()
    {
    	list<int> *l1=new list<int>;
    	l1->add(22222);
    	l1->add(1);
    	l1->add(11);
    	l1->add(11);
    	l1->add(111);
    	l1->add(11);
    	l1->add(1111);
    	l1->add(11111);
    	l1->show();//打印链表数据
    
    	list<int> l2;
    	l2.add(2);
    	l2.add(3);
    	l2.add(66666);
    	l1->merge(l2);
    	l1->show();
    
    	l1->rev();
    	l1->show();
    
    	l1->deletesame();
    	l1->show();//打印链表数据
    	
    	l1->sort();
    	l1->show();//打印链表数据
    
    	l1->getnum();
    
    	l1->change(l1->find(11), 12);//替换结点数据
    	
    	l1->deletel(1);//删除
    
    	l1->show();//打印链表数据
    
    	l1->deleteall();
    
    	l1->show();
    
    	delete l1;
    	cin.get();
    }
    //十字链表
    //链表存储的数据链表
    void main()
    {
    	list<int> *l1 = new list<int>;
    	l1->add(22222);
    	l1->add(1);
    	l1->add(11);
    	l1->add(11);
    	l1->add(111);
    	//l1->show();//打印链表数据
    
    	list<int> *l2=new list<int>;
    	l2->add(2);
    	l2->add(3);
    	l2->add(66666);
    
    	list<list<int>*> *l3 = new list<list<int>*>;
    	l3->add(l1);
    	l3->add(l2);
    
    	l3->phead->data->show();
    	l3->phead->pnext->data->show();
    
    	cin.get();
    
    }
    
    

    4.哈希存储

    容易查找,不易于插入和删除 O(1)

    #pragma once
    
    template<class T>
    class hashnode
    {
    public:
    	int key;//代表索引
    	T data;//数据
    	//int count;//查找次数
    };
    /*
    索引 
    数据
    */
    #pragma once
    #include "hashnode.h"
    #include<string>
    using namespace std;
    template<class T>
    class mhash
    {
    public:
    	hashnode<T> *p;///哈希表
    	int n;//长度
    public:
    	mhash();
    	~mhash();
    	int myhash(int data);
    	void init(T *pt,int nt);
    	bool isin(int key,T t);
    	hashnode<T> * find(int key);
    	
    };
    
    #include "mhash.h"
    #include<string>
    using namespace std;
    
    template<class T>
    mhash<T>::mhash()
    {
    	this->n = 10;
    	this->p = new hashnode<T>[this->n];
    }
    
    template<class T>
    mhash<T>::~mhash()
    {
    	delete[]p;
    }
    //获得哈希表索引值
    template<class T>
    int mhash<T>::myhash(int data)
    {
    	return data % n;
    }
    //哈希表简单初始化
    template<class T>
    void mhash<T>::init(T *pt,int nt)
    {
    	for (int i = 0;i <10;i++)
    	{
    		p[i].key = pt[i]%n;
    		p[i].data = pt[i];
    		//p[i].count = 0;
    	}
    }
    //判断数据是否存在
    template<class T>
    bool mhash<T>::isin(int key,T t)
    {
    	if (p[key].data ==t)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    //查找
    template<class T>
    hashnode<T> * mhash<T>::find(int data)
    {
    	int res = myhash(data);
    	return p +res;
    }
    #include<iostream>
    #include "mhash.h"
    #include "mhash.cpp"
    #include "hashnode.h"
    
    using namespace std;
    //哈希表简单原理
    void main()
    {
    	mhash<int> myh;
    
    	int a[10] = {10,11,22,33,44,55,66,77,88,99};
    
    	myh.init(a,10);
    	cout << myh.isin(4,44) << endl;
    	hashnode<int> *p = myh.find(99);
    	cout << p->key << endl;
    	cout << p->data<< endl;
    
    	cin.get();
    }



    展开全文
  • MySQL哈希索引的数据结构以及索引的优缺点

    千次阅读 多人点赞 2021-08-03 11:27:39
    MySQL哈希索引结构的实现,以及索引的优缺点

    上一篇文章中,我们专门介绍了BTREE索引的数据结构以及底层实现,现在我们看看其他哈希索引结构的实现,以及索引的优缺点。

    1 索引的优缺点

    索引可以让服务器快速的定位到表的指定位置。但是这并不是索引的唯一作用,总结下来索引有以下4个优点:

    1. 索引大大减少了服务器需要扫描的数据量。
    2. B-Tree索引可以帮助服务器避免排序和临时表,可以用于 ORDER BY 和 GROUP BY 操作,临时表主要是在去重、排序、分组过程中创建,不需要排序和分组,也就不需要创建临时表。
    3. 由于索引中存储了实际的列值,所以某些查询可以只使用索引就能完成全部查询,甚至避免回表查询。
    4. B-Tree索引数据都是有序的,可以将随机I/O变为顺序I/O,顺序读取不需要进行磁盘寻道,并且只需要很短的磁盘旋转时间,速度会非常快。并且可以利用预读特性,相邻的节点也能够被预先载入。

    索引的缺点:

    1. 索引本身也是表,因此会占用存储空间,创建和维护索引需要耗费空间和时间成本,这个成本随着数据量增大而增大;
    2. 构建索引会降低数据表的修改操作(删除,添加,修改)的效率,因为在修改数据表的同时还需要修改索引表。

    大多数情况下,中到大型的表索引查询都是比全表扫描要快的。但是对于非常小的表(数据量很少),那么简单的全表扫描更高效。

    但是对于特大型的表,建立和维护索引的代价将会随之增长。这种情况下,需要用到一种技术可以直接区分出需要查询的一组数据,而不是一条记录一条记录地匹配,例如可以使用分区技术。

    2 哈希索引

    哈希索引(hash index)基于哈希表实现。哈希索引通过Hash算法(直接定址法、平方取中法、折叠法、除数取余法、随机数法)将数据库的索引列数据转换成定长的哈希码作为key,将这条数据的行的地址作为value一并存入Hash表的对应位置。

    在MySQL中,只有Memeory引擎显式的支持哈希索引,这也是Memory引擎表的默认索引结构,Memeory同时也支持B-Tree索引。并且,Memory引擎支持非唯一哈希索引,如果多个列的哈希值相同(或者发生了Hash碰撞),索引会在对应Hash键下以链表形式存储多个记录地址。

    哈希索引还有如下特点:

    1. 哈希索引不支持部分索引列的匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如,在数据列(A,B)上建立哈希索引,如果查询只有数据列A,则无法使用该索引。
    2. 哈希索引具有哈希表的特性,因此只有精确匹配所有列的查询对于哈希索引才有效,比如=、<>、IN(,因为数据的存储是无序的),且无法使用任何范围查询。
    3. 因为数据的存储是无序的,哈希索引还无法用于排序。
    4. 对于精确查询,则哈希索引效率很高,时间复杂度为O(1),除非有很多哈希冲突(不同的索引列有相同的哈希值),如果发生哈希冲突,则存储引擎必须遍历链表中的所有数据指针,逐行比较,直到找到所有符合条件的行。哈希冲突越多,代价就越大!

    基于以上的限制,哈希索引只适用于某些特定的场合,但是一旦适合哈希索引,则它带来的性能提升是非常显著的。

    InnoBD引擎有一个特殊的功能叫“自适应哈希索引”。当InnoDB注意到某些索引值被使用得非常频繁时,它会在内存中基于B-Tree索引之上再创建一个哈希索引,这样就让B-Tree索引也具有哈希索引的一些优点,比如快速的哈希查找。但这是一个完全自动的、内部的行为,用于无法控制,但用户可以选择完全关闭该动能。

    在使用InnoBD引擎时,我们可以在B-Tree的基础上创建一个伪哈希索引。当然这不是真正的哈希索引,因为还是使用的B-Tree进行查找,但它使用哈希值而不是键本身进行索引查找。

    例如,如果需要存储大量的URL并且需要根据URL进行查找,如果使用B-Tree来存储URL,则存储的内容就会很大,因为URL本身就很长。为此,我们可以单独指定一个哈希列并为该列创建索引,并选择一个哈希函数!每次存储、变更URL时,对该URL应用一个函数计算出一个哈希值,存入对应的哈希列中。

    在查询时,如果采用体积很小的基于哈希值的索引来查找,则性能会提升很多,唯一的缺点就是需要调用一个哈希函数,为此我们可以使用触发器来实现。

    如果出现了哈希冲突,则查询会返回多行数据,为此在查询时还必须带上真正的URL常量值。正确的查询语句为:

    select xx from url where url_hash = hash('https://www.baidu.com/') AND url = 'https://www.baidu.com/';
    

    3 全文索引

    全文索引是一种特殊类型索引,用于查找文本中的关键词,而不是直接比较是否相等。全文索引的和其他索引的匹配方式完全不一样,全文索引更类似于搜索引擎做的事情,查找条件使用 MATCH AGAINST,而不是普通的 WHERE。

    全文索引使用倒排索引实现,它记录着关键词到其所在文档的映射。

    MyISAM存储引擎支持全文索引,InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。

    4 空间数据索引(R-Tree)

    MyISAM存储引擎支持空间数据索引(R-Tree),可以用于地理数据存储。空间数据索引会从所有维度来索引数据,可以有效地使用任意维度来进行组合查询。

    必须使用 GIS 相关的函数来维护数据。

    下一篇文章中,我们将介绍一些高性能的索引策略以及索引失效的情况和索引优化策略,在面试中会经常问道。

    参考资料:

    1. 《 MySQL 技术内幕: InnoDB 存储引擎》
    2. 《高性能 MySQL》

    如有需要交流,或者文章有误,请直接留言。另外希望点赞、收藏、关注,我将不间断更新各种Java学习博客!

    展开全文
  • 常见数据结构优缺点

    千次阅读 2018-12-02 22:23:53
    通用数据结构: 1.数组 分类: 无序数组,有序数组 特点: 一般针对数据量较小且数据可预知的情况,创建时指定大小,不利于扩展;在内存中预留一块连续的区域,内存空置率高利用率较低;无序数组插入较快,...

    通用数据结构:
    加粗样式

    1.数组
    分类:
    无序数组,有序数组
    特点:
    一般针对数据量较小且数据可预知的情况,创建时指定大小,不利于扩展;在内存中预留一块连续的区域,内存空置率高利用率较低;无序数组插入较快,有序数组查询较快,利用下标访问,随机访问性强。
    优点:
    查询速度快
    随机访问性强,遍历数组方便
    缺点:
    内存固定,扩展性差
    数组要预留空间,内存利用率低
    插入删除速度慢
    只能存储一种类型的数据

    2.链表的特点:
    分类:
    单链表、双向链表以及循环链表
    特点:
    创建时不指定大小,内存大小随数据量变化;内存的存储位置可以在任何地方,不要求连续,可扩展性强;每一个数据保存邻近的数据的地址,遍历需要从根节点开始,没有随机访问性,查找效率低;增加删除比较随意,效率高。
    优点:
    插入删除速度快
    内存利用率高,不浪费内存
    存储的数据类型相对灵活
    大小不固定,扩展性强
    缺点:
    查询速度慢
    只能从根节点开始查找,不具备随机访问性

    3.二叉查找树
    分类:
    平衡二叉树,非平衡二叉树
    特点:
    结合数组和链表的优点,适合数据量较大的情况,具有一定顺序,左子节点值较小,右子节点值较大;查找时从根节点开始,不具备随机访问性,但相比较而言查询速度快,增删速度快,对于遍历一定范围内的数据比较方便。非平衡二叉树简单,但对于部分数据查询增删效率较低,甚至会退化成链表。
    优点:
    查询增删速度快
    存储的数据类型相对灵活
    不指定内存大小,内存利用率较高
    缺点:
    只能从根节点开始查询,不具备随机访问性
    对于部分数据,给平衡二叉树的效率会向链表结构靠拢

    4.平衡树
    实现:
    AVL树、红黑树、2-3树等
    特点:
    改善了二叉搜索树的缺点,实现起来稍微复杂,平衡树结构会产生了额外消费,但查询及增删效率均比较高
    优点:
    查询速度较快
    增删速度较快
    存储的数据类型相对灵活
    不指定内存大小,内存利用率较高
    缺点:
    实现起来复杂
    会产生一定的额外消费

    5.哈希表
    实现方式:
    开放地址法、链地址法
    优点:
    插入删除速度最快
    缺点:
    基于数组,创建后扩展性差
    弱序,查找速度慢
    基于哈希映射,会有冲突产生,并形成数据聚集
    需预留内存,内存利用率不高

    通用数据存储结构的速度
    在这里插入图片描述

    参考资料 《java数据机构和算法》

    展开全文
  • 平台可信实体的散列值以非平衡哈希树叶子节点的结构存储,远程验证时,查找度量实体对应的叶子节点,记录该叶子节点到根节点的验证路径,然后传递根节点和验证路径给验证方,最后根据验证路径重新计算根节点来验证...
  • 我觉得需要先梳理相关的概念,国内部分的教材,概念可能因为计算机理论的快速发展和更新而变得比较模糊和陈旧(有些教材因为编纂比较...本身可以对应多种数据结构,其中最具代表性的就是数组(array)和链表(linked li
  • 还可以用来制作缓存,在没有redis等缓存手段的时代使用哈希存储结构来制作缓存的 看一条题目: 索引存储: 除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。 特点: 索引存储...
  • 哈希优缺点哈希的核心思想? 线性表和树数据的存储位置和数据的具体数值之间不存在任何关系。因此,在面对查找问题时,这些数据结构必须采取逐一比较的方法去实现。而哈希表的设计采用了函数映射的思想,将...
  • 哈希结构缺点

    万次阅读 2016-10-02 01:08:42
    哈希表也有一些缺点:它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序虽必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的...
  • 1、对象数据组成结构 与块存储和文件存储管理数据的方式不同,对象存储是以对象的形式管理数据的。对象和文件最大的不同,就是在...块存储的数据结构是数组,而文件存储是二叉树(B,B-,B+,B*各种树),对象存储基本上
  • 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 相对于顺序表来说,链表按需申请空间,不用了就释放空间,更加合理的使用了空间。 ...
  • 红黑树与哈希表的比较(数据结构!)

    千次阅读 2020-04-11 10:22:31
    就拿哈希表来举例,在刚学数据结构的时候,最基本的数据结构是数组,他拥有随机访问元素的能力,但是元素的存储是紧挨着的,这就导致他的插入和删除的时间复杂度较高,因为添加删除一个位置的元素需要将后面的所有...
  • 缺点:在中间部位添加、删除比较复杂,大小固定,只能存储一种类型的数据; 如果应用需要快速访问数据,很少插入和删除元素,就应该用数组。 链表(LinkedList): 优点:有序添加、增删改速度快,对于链表数据...
  • 块/文件/对象三种存储优缺点

    千次阅读 2019-09-27 19:04:36
    从应用角度看块/文件/对象三种存储:http://www.talkwithtrend.com/Article/178247 对象存储从理论到实践:...对象存储、文件存储、块存储,从应用角度看有何不同?“狠角色”们是怎么搭配的?:h...
  • 散列表是一种空间换时间的存储结构,是在算法中提升效率的一种比较常用的方式,但是所需空间太大也会让人头疼,所以通常需要在二者之间权衡。我们会在之后的具体算法章节中得到更多的领悟。 什么是散列表 让我们想...
  • 散列(hashing)是一种重要的存储方法,也是一种常见的查找方法。 基本思想:以结点的关键字k为自变量,通过一个确定的函数关系f,计算出对应的函数值,吧这个函数值解释为结点的存储地址,将结点存入到f(k)所指示的...
  • 存储在连续内存上;内容都是相同类型;可以通过下标访问。 缺:必须指定其长度,元素插入也不方便(过长浪费内存,多段会溢出) ArrayList(数组) 相当于Array的升级版 :可动态增加和删除 ,可存储不同...
  • 数组、链表、Hash的优缺点

    千次阅读 2019-06-12 15:17:00
    链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。 2、数组必须事先定义固定的长度,不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存...
  • 文章目录一、哈希表1.哈希表概念2.冲突的概念3.避免冲突与解决冲突3.1 避免冲突的方式1——哈希函数的设计3.2 避免冲突的方式2——负载因子的调节3.3 解决冲突的方式1——闭散列3.4 解决冲突的方式2——开散列、哈希...
  • 哈希结构 哈希概念 常见的K-V结构,实现了元素... 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素 哈希
  • 【数据结构哈希表 详解

    千次阅读 2022-02-23 17:53:45
    哈希表 详解
  • 各种数据结构优缺点分析

    千次阅读 2016-10-27 00:38:06
    缺点:查找慢,删除慢,大小固定 有序数组 优点:比无序数组查找快 缺点:删除和插入慢,大小固定 栈 优点:提供后进先出的存取方式 缺点:存取其他项很慢 队列 优点:提供先进先出的存取方式
  • 数据结构---哈希(Hash)

    千次阅读 2021-06-16 20:08:51
    哈希1. 哈希概念2. 哈希函数3. 哈希冲突3.1 闭散列3.1.1 闭散列模拟实现3.2 开散列3.2.1 开散列模拟实现4. 基于开散列实现unordered_set5. 基于开散列实现unordered_map6. 闭散列和开散列对比7. 哈希的应用7.1 位图 ...
  • 各种树的优缺点

    2021-07-15 09:43:54
    树 二叉树 平衡二叉树 B树 B+树 面临的问题: 哈希索引问题 ...1-哈希索引问题 ...因为哈希值是一个无序值,所以...B树结构:B 树的所有节点既存放键 (key) 也存放数据 (data),而 B + 树只有叶子节点存放 key 和 data,
  • 四种存储结构及其特点

    千次阅读 2019-11-06 16:00:02
    存储结构 数据元素之间的关系在计算机的存储有四种表示方法,分别是顺序存储、链式存储、索引存储、哈希存储。 特点 顺序存储 数据元素顺序存放,每个结点只有一个元素。存储位置反映数据元素间的逻辑关系。存储密度...
  • 各类数据结构之间的优缺点对比

    千次阅读 2020-03-05 12:09:00
    什么是数据结构 ...各数据结构之间的优缺点对比 数据结构 优点 缺点 数组 插入快,如果知道下标,可以非常快的存取 查找慢,删除慢,大小固定 有序数据 比无序数组查找快 删除和插入慢,大小固...
  • 一.数组、字符串 为什么把字符串和数组放在一起...1.2缺点 构建时必须分配一段连续的空间 查询某个元素是否存在时需要遍历整个数组,耗费O(n)的时间,n为元素的个数 删除和增添某个元素时同样需要耗费O(n)的时间 1...
  • 逻辑结构和存储结构

    千次阅读 多人点赞 2017-08-16 17:41:25
    什么是逻辑结构?  简单说,逻辑结构就是数据之间的关系。而按数据之间的关系来说,逻辑结构大概可以分为两种:线性结构和非线性结构(集合、树、网)。 线性结构:有且只有一个开始结点和一个终端结点,并且所有...
  • 数据的逻辑结构和存储结构

    千次阅读 2019-08-26 22:30:34
    数据的逻辑结构合存储结构 一,逻辑结构 数据的逻辑结构是对数据元素之间逻辑关系的描述,它与数据在计算机中存储方式无关,根据数据元素之间的不同特性,可以对数据的逻辑结构进行分类 分类1:(选型结构和非线性...
  • 因为Hash索引底层是哈希表,哈希表是一种以key-value存储数据的结构,所以多个数据在存储关系上是完全没有任何顺序关系的,所以,对于区间查询是无法直接通过索引查询的,就需要全表扫描。所以,哈希索引只适用于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 63,821
精华内容 25,528
热门标签
关键字:

哈希存储结构的优缺点